How can I open a frozen padlock? Spraying WD-40 didn't help and I don't have access to deicer spray at the moment. I'm not sure what else to try.
If you have a high-proof alcoholic beverage (not sweet; sugar will gum up the works later), that can work as deicer, but dry out the lock afterwards.
Use a hair dryer. The warm, dry air from a hair dryer is perfect for melting ice. Depending on how frozen the lock is and the outside temperature, it may take between one and five minutes, if not longer.
Then spray the lock with WD-40 to help prevent it from happening again.
If you are miles from anywhere and you don't have anything with you described above and your survival depends on what's on the other side of the door there is a fairly unsavory way to thaw the lock to allow you to operate it; urinate on it. It's not pleasant but it will raise the temperature of the padlock and thaw any ice in the mechanism.
Heat the key with a lighter. Then stick the key in the lock. Works every time.
To add to the other answer that may not be as accessible due to the length of a Hair Dryer cord, here is what I do:
Wrap the lock in your hands and breathe on it. Use your hands to insulate the heat in. This usually opens it, and I usually take it somewhere warm to thaw out and apply the WD-40.
Other methods are if the lock is pure metal is to put a fire(cigarette lighter, etc) directly to it. The below link says to use a mug of a hot beverage. But from experience the hot liquid will be steam and if the weather is cold enough, this will turn to ice when it the lock. But if hold it close enough and have some barriers around it to protect against wind then it should work.
Another option building on the heat line of thoughts, is to use one or two plastic bags filled with warm water, and then put these in contact with the padlock, i.e. one on either side.
Leave for a few minutes, and the padlock should have thawed and be easily opened again!