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.