Use what is called a "Make Up Air Unit". These propane or natural gas heaters heat the outside air with the flame outside, then they blow the heated air to the inside of your building.
Your local Farm AG Service has them, they are called Hog Barn Heaters.
They heat an area up real fast. My concern with painting in a building that is not a controlled paint booth is moving air around real fast and getting dirt in the nice new paint.
