I think that for low temperature performance, nickle-cadmium is the best rechargeable chemistry that is readily available to a consumer.
For primary cell chemistry, 1.5V lithium cells have a great reputation for performance in the cold.
My personal experience is that lithium rechargeables are a waste of time below about 5C.