Erik, I had really good luck using a light oil and heating the hinges with a propane torch. One side goes in the vice and the other in a crescent wrench or you hit it with a hammer. Whatever it takes to get the thing moving. Dab the oil in the gaps around the pin. After about 10 minutes of adding more oil, keeping it hot, and bashing the thing through its travel arc, you will probably have it moving pretty freely. This technique seems to "boil" out the rust. Be prepared to clean it well and sand blast before attempting to paint.

Doing this, I took all of my door hinges from frozen solid to flopping back on themselves. Havent noticed any ill effects.

Good luck,
Josh