If you want small but powerful batteries, consider a lithium CR2. Each cell is 3V nominal, and you could clock your Atmega328 at 8MHz or lower and run directly from it. If your LED is a little 5mm / 20mA job, it could also probably run directly from a single CR2... for a while. Technically you don't have enough Vf but in reality you can often bend the spec a little for low-power LEDs (they're just a little dim, adjust the resistor to compensate). But as the CR2 discharges and voltage drops over time, the blue and green will probably poop out before the red and the Atmega itself quit working. But maybe that's a "low battery indicator" feature.
Another alternative would be a pair of CR2032s (lithium coin cells). You would be over-volting the Atmega with fresh cells (over 6v), so perhaps a 5.6V zener could reduce the voltage by wasting power for a few minutes until the cells naturally discharge a bit.
If you're going to be using this a lot, consider a rechargeable Li-Po or Li-ion cell. They come in various small form factors (Li-ion is available in 10180 or even 2032 form factors) and run at a more convenient 3.6v. However, you MUST use a proper charger or smoke and flames will result. You'd also want to use the ADC on the Atmega as a voltmeter and shut itself off when appropriate to make sure you do not over-discharge the cell.