I've had a gas-fired, forced-air heater in a couple of different garages. They work very well and don't cost all that much to operate. My most recent heater purchase was a Hot Dawg heater by Modine. It's rectangular in shape and only requires 1" of clearance to the sheetrocked ceiling. The blower fan doesn't draw much juice so it shouldn't require a dedicated circuit.
I haven't had a chance to install heat in my current garage, but I plan to before this winter. I'm also planning to have the cheapo tin garage door replaced with a new R-18 insulated garage door.
Personally, I think it's worth the cost and hassle to install a natural gas line to the garage because I think in the long run the lower operating costs will outweigh the lower initial installation cost of an electric heater. It sounds like you don't have enough electricity to run an electric heater anyway so you'll have to run one or the other.
The nice thing about having a good forced air gas heater is that the recovery time is fairly quick. I keep my hangar at 40 degrees minimum all winter. Even on the coldest day, I can walk in and have sweatshirt temps within 10 minutes. The garage is even better because it's fewer cubic feet to heat.
For what it's worth...