I bit of research indicates you may find a Li-Ion battery that will work at -40C.
If it is going to get colder than that you may need to go with your "heated box" idea, at least to bring the temperature up a bit.
However I presume that this very issue confronts people in the Arctic and Antarctic, so there must be documentation about it around.