You have to send your car the signal to preheat within 100m or 300 feet of the car, so you won't be able to preheat until you are back at the station.
MLucas is right, you can program charging ahead of time but not heating/cooling. I knew that yet I still gave you bad info. Senior moment I guess...
Sandage, I agree with you that running the car heater during extended travel time due to bad weather/traffic is a big concern especially with the temperatures and other info you've identified. Ouch. However, I see that the propane heater you linked to works from a flame. If you really are considering a propane heater you should look at the catalytic type. Take a look at this study:
Let us know what you decide.