Supplying steady 5v to the board from inconsistent battery pack

My project requires controlling a relay module from Espruino, and to be powered by batteries in cold temperatures. At room temperatures, so far everything works great by connecting 4 AA cells (about 6 volts) to the Espruino. The relay comes on fine. However, at cold temperatures (< 0 degrees C), the voltage in the battery pack drops to around 4 volts. This is not enough to flip the relay and power the board and the connected items. (I tried alkalines and lithiums - lithiums hold out a bit longer but eventually succumb to same problem).

I tried using a 9 volt battery, but this is TOO much for the relay module, and it just stays on.

My next thought is to use a voltage regulator, and run 6-8 cells (9 volts or 12 volts) on the battery pack. This way, the Espruino would get a steady 5v no matter what wide variances in voltage come from the battery pack.

Then I thought something from these guys (http://www.digikey.com/product-highlights/us/en/cui-v78-regulators/1177) would do the trick. Something like the V78-500-SMT: http://www.cui.com/product/resource/v78-500-smt.pdf

So:

1. Is this the right approach?
   
2. Would the linked component work, presuming I add on those capacitors mentioned in the "TYPICAL APPLICATION CIRCUIT" section?
   
3. Is there some module that is ready made (e.g. no assembling a bunch of capacitors) that would be better suited to the task?
   
   

Thanks!