In the UK, it's still fairly easy to get hold of Sturmey Archer 3 speed hubs. These run with oil rather than grease, so should cope just fine with sub-zero temperatures. The shifters are robust and reliable and shouldn't get snarled up with ice - they are a very open metal design, so you can dribble oil into them to keep the water/ice out.
An SA AW hub would make for a great winter bike. I fitted one to an old track frame and used it for years, riding year round in really hilly areas.