I live in Anchorage and we typically get -20F for a week or two a year, so I have a feel for what you speak.
I've attached a PDF with some "talking numbers" on heat loss. I say "talking numbers" because, despite my BS in Mechanical Eng., it's not the discipline of engineering I practice. I encourage you to go to a professional engineer to refine these numbers or go to a web site and calculate them yourself, this is just so we can talk "size of the breadbox" stuff.
All calculations are based upon assumptions. This calculation assumes R-11 insulation in the walls (4" fiberglass), R-19 in the roof (6"), concrete floors and 10 sq. ft. of windows. Windows lose a lot of heat, although they are nice to have. Also, this allows for one air change per hour. That is a rule of thumb for fairly well-constructed existing construction. Based upon that, with a -20F outside and 65F inside, the building would lose ~27,000 BTU/hr steady-state. If it was -20F inside and you wanted to warm up metal tools in a reasonable amount of time, you'd need more for a while.
You talk of electricity and propane. Electricity may well be the best solution if it is just temoporary (i.e. you're renting), as the initial investment is minimized though the hourly electric bill, when it was -20F outside, would be about 9 kwh. At $0.12/kwh, this would be about $1.00 per hour, although if the initial cost could be as low as the price of 6 portable heaters (~$20 each, less on sale). In order to do this though, you will need lots of power available in your shop. This would take 6 each 20A breakers with wiring, as each heater will require its own breaker. If you need to run a subpanel to make this work, your price goes up.
If you own the home, the best bet will be to set yourself up to eventually use natural gas, though it is not necessary right at first. I'd look for a direct-fired, exhausted, garage heater. T oget 30,000 BTU's I'd go with a 40,000 or 50,000BTU input furnace, as some of the heat goes up the chimney. They are available that can be made to run off of propane or natural gas (change of jets). This would permit you to get up and running on propane and then swap over if the price of propane becomes an issue. You can either operate off of a 100# tank or get your local propane delivery service to rent you a larger one. A 100# tank should last somewhere around 25 - 40 hours of burner-on time. You will need to check on propane prices, they vary widely by location.
What you *don't* want is a non-vented heater at those kind of temperatures combined with that size of burner. When propane is combusted, the result of perfect combustion is CO2 and H2O (water vapor). The last thing you want is warm water vapor condensing on your cold tools.
As you might guess, garage / shop heating is a popular topic here in Alaska. :-)
There are some here who heat their shop with a wood stove. It's nice dry heat, if you have the time to spend cutting and stacking your own wood. It also has disadvantages when you are finishing and you need to keep the place warm for an extended time for the finish to cure. If you have to buy your firewood, all bets are off.
Just my $0.02...
Check out that new high-tech cordless router.. wireless and no recharging required!!