The ATMEL 168/328 will run on quite a range of voltages. Using NiMH batterries there shouldn't be an issue wiring 4 of them straight to the 5v input. Providing the voltage doesn't go above 5.5v it should be OK. If you're using Alkalines use 3 cells instead of 4. they are quite happy running at 3 volts, whether the same can be said of the circuits that are powered from the arduino is a different matter.