Not Ni-Cd - I'd go for Nickel Metal Hydride, NiMH. Similar voltage, but without NiCad's memory problem.
Can get 2500mAH AA cells, last a long time.
Logic High in or out will depend on Vcc. A '328P will be fully in operational compliance at 16 MHz with Vcc down to 3.78V, and things may or may not get funny below that.
Vih & Voh are dependent on Vcc, with a valid high in needing to be 0.7 x Vcc, and a high out guaranteed to be 0.8V to 0.7V below Vcc, Vcc & load dependent.
See section 32, 32.2. Common DC Characteristics
of the datasheet, the latest is dated Nov 2016 http://www.atmel.com/devices/ATMEGA328P.aspx
I stand corrected on the logic levels and NiMH is certainly a more "energy dense" battery but every other characteristic of NiMH is inferior. Most people nuke them just trying to charge them. They are very poor at handling fast or overcharging whereas NiCd can be recharged over 1000 times at up to 4C safely and will provide long life even when abused. AA cells are also available in a 600 mAh capacity which should yield the 10 hr min the OP is looking for. Given the 5V requirement of these boards, a battery with 1.2V nominal voltage is more convenient than any other battery type (fact) because you don't need to regulate it at 4.8V and if you go to 3 decimal places, these batteries often hover a little above that at low discharge rates of 1/10 C. Compare this to alkaline (4.5V), lead acid (4V), lithium (3.7V) and it's clearly the closest match. Plus you can:
-operate the battery in the most extreme range of temperatures
-discharge it to 0V without damaging it
-maintain a safe operating voltage for most of the batteries life without voltage drift
-use it over and over again for at least 1000 cycles
-charge it quickly (4C) without any damage
NiMH basically has the advantage of greater capacity but has none of the other benefits
The nefarious "memory" effect was observed in space satellites on a charge cycle that coincided with its fixed orbital period after many cycles and the only effect was a momentary drop in voltage at the point where the charge normally terminated. This effect is 100% reversible by deep cycling and is very hard to reliably reproduce in consumer applications because the phenomenon only shows itself with repeatable and frequent incomplete charging. It is mostly popularized hype with negligible importance in real-world battery usage.
Suggested Cell: Panasonic (Sanyo) N-600AAC