Before putting any heat in, you need insulation. You'll just be beating yourself up if you try heating the space with no insulation.
With that being said, I heat my 28' x 36' garage with a 45,000 btu ceiling mount heater, and run it off of a 120 lb. propane tank. If it is a possibility, you could go that route.
My wife has a 20' x 20' building that she uses for a greenhouse, crafts, or whatever. Her building is insulated and drywalled and she uses two of the oil filled radiators that you can get at the boxstores. When it's in the 20's, she uses one on medium heat and it will keep it at a very comfortable 70f degrees. If it gets below zero, she will put the other on medium and run two and it will still maintain 70 degrees.