Anyway you want that ends up with 4-5 volts on the atmega power pins. 3 AA alkaline batteries, 4 rechargable AA batteries. Lesser # of batteries and a boost regulator chip. Bigger battery and a 7805 type regulator, or a switching type step-down regulator (check out the selection at pololu.com or the equivalent in whatever part of the world you're in).
3.7VLi battery if running at 8MHz vs 16. What else do you have going on around it?