In addition to the VCC ratings of 1.8V to 5.5V, max 6V as mentioned by Dejvid_no1, there is another issue with voltage levels on VCC.
As your raw, unregulated battery voltage is being used as the system VCC reference, this means that any logic signals on the inputs and outputs will be affected along with it. If at full battery your voltage is 4.2V for example, off a single cell Li-Po battery, you will not be able to receive logic "HIGH" from 1.8V devices like GPS transmitters etc. However as the battery drops in voltage, the comparison level for "HIGH" and "LOW" changes and will eventually pick up the signals. This happened to me in a low power battery into VCC rail application!
The other issue is clock speed. The ATMEGA328 datasheet specifies minimum VCC voltage levels for certain clock speeds, to guarantee correct operation. If you want < 10MHz, or want to use the internal 1Mhz oscillator, then you can give it whatever you want in that allowable VCC range - but if you want to use 10+Mhz and external crystals etc, you must supply it with 4.5V+. Please double check the datasheet for the exact voltage requirements and clock speed - there is a table/chart with the speed and voltage listings.
Obviously you'd need the full 5V for the maximum rated clock speed of 20Mhz but your application being low power battery operated hopefully does not need such high clock speeds.
edit:
Also, the regulator on those boards are linear regulators, which literally burn the difference in voltage as heat. I strongly suggest you avoid putting anything more than 12V on any "arduino" product, as they all use linear regulators - dropping 7V and using any reasonable power will blow up the regulator pretty fast.
If you ever get into your own PCB making, for example your own custom pro-mini style board, I suggest you look at the Texas Instruments "Simple Switcher" and similar lines of DC-DC Switchmode power converters which are very low part count, and easy to use. They are 85-90% efficient in most cases, rather than 35-40% like the linear ones with inputs at ~12V. DC-DC converters often allow quite high inputs, like 36-40V, down to your 5V or 3.3V output, so they are pretty amazing once you learn how to use them.
