You could use a 5v volt regulator, and thus get a steady 5v supply.
You could also yank the crystal of the arduinos and use the internal oscillator, which brings the arduino down to 8mhz, and then provide it with 3v3 on the vin pin, this essentially makes it an 3v3 8mhz arduino.
If you power it with 4 batteries and you disable the power led you should get fairly long battery life, regardless of the required voltage of your setup.
If you are uncomfortable with modding your arduinos, I suggest you look in to low dropout volt regulators.