Do you really need 5v?
An Uno or Mega will happily run on 4.5v from 3 x AA alkaline cells connected to the 5v pin. I have not tried it with 3 x AA NiMh cells which would only be 3.6v. Nor have I tried it on 4 x AA NiMh cells which produce 4.8v and should be OK. However I don't know if there is a risk of exceeding 5v while charging 4 x AA NiMh cells.
Another option is to build a breadboard Atmega 328 using its internal 8MHz oscillator - that will run happily on 2 x AA alkaline cells or a 1s LiPo. It should also be quite happy with 3 x AA NiMh cells.
...R