Low temperature batteries for use in Arctic
Some Lithium primary cells are rated for military temperature range (down to -55°C). Check out the Israeli company Tadiran. 

Maybe you can combine the primary cells with rechargeable cells to extend the life, just ensure that the storage temperature of the rechargeable cells includes your lower limits. 

You could also consider insulating the battery and using some of the battery power to keep the battery itself warm enough. This could cause problems with overheating during charging conceivably but maybe slow charging is acceptable since more hours of light are available when the temperatures begin to rise. This also works for LCD displays that need to work in extreme cold (film heater attached to the back of the display). 
There might be a fix with a damper and/or ducted fan too. 

The ultimate solution is an RTG, but that's probably impractical for you.