I would not recommend the lithium batteries for low temperature applications. They suffer badly from low temperature, more than either the alkaline or NiMH chemistries.
I'd recommend Nickel-Cadmium (Ni-Cad) batteries, as they have have the best temperature range of any of the typical batteries, They also have very low internal resistance (less than half that of a NiMH) and therefore have very good maximum currents (think of an electric drill).
Some things to watch out for are their memory characteristic (Don't recharge it before it's almost dead, or you'll lose the capacity you don't use) and the fact that they contain toxic cadmium. Use a decent charger or charge IC, and you'll be fine. You might have some trouble trying to do a dT(emp)/dt(ime) cuttoff, and they don't have a great -dV/dt characteristic either.
Another idea (if you own the fridge) - Can you just open up the temperature control panel and light at the back of the fridge, get at the power source, say, for the light (before the switch, if you want it to be running when you close the fridge), and stick in an outlet or a couple (INSULATED! WELL INSULATED!) spade terminals and plug in a wall wart? That's what I'd do, rather than messing with batteries.