Power Arduino Mini with 3 AA batteries
You can connect 2 or 3 1.5V cells or 2 to 4 1.2V cells between 5V and GND. You will have to limit your speed though, depending on exactly what you want to run it off of. Section 29.3, "Speed Grades", of the ATmega48A/PA/88A/PA/168A/PA/328/P datasheet shows the relation between supply voltage and maximum clock rate (note that the device may run above the speed at a given voltage, but this is not guaranteed).

It is possible to start at, say, 2MHz with the 16MHz crystal and the CLKDIV8 fuse, and then ramp up (or down) the prescaler based on the voltage available, but check that the libraries you're using can handle the clock rate being changed under them first.

And I recommend you take advantage of the power reduction features available; see section 10, "Power Management and Sleep Modes", of the datasheet for details.