Small batteries for use in cold (but not freezing) environments?
I would suggest a lithium CR2032 battery. feel free to pick a large package or place a few in parallel.

Lithium Polymer will have lower capacity at lower temperatures.

However, to quote battery university, 


  "Lithium-ion  works within the discharge temperature limits of -20°C to 60°C (-4°F to 140°F)."


As a side note, they often list 1mA as maximum current on one of these, but they can handle 10mA without much of a battery life loss(this will be worse at lower temps), pass 10mA and you will be killing batteries right and left.

Here is an example of a discharge curve based on temperature. It is the second page of the data-sheet. There is a clear decrease in life(~25%), but you should still be very able to use the battery. It looks like -20 degrees C is where you start to have large reductions.

Please let me know if there is anything I can add to make this more clear or more valuable to you.