The Arduino website it recommends 7-12V as the unregulated safe input range for the Arduino's regulator. Here are the specs for the regulator:
Minimum input voltage: 6V
Absolute Maximum input voltage: 20V
Maximum output current: 800mA
More info here:http://pdf1.alldatasheet.com/datasheet-pdf/view/12048/ONSEMI/MC33269D-5.0.html
It's voltage drop out is 1V, and since it regulates a 5V output, running it on four AA batteries at 6V won't last you long once their voltage drops below 6V. You could try using 9V batteries although you won't have much Amp Hours to work with.
You could also use 7.2V Lithium Poly batteries, although they are relatively hard to get and finding a charger for them is equally hard.
Since you already have a 12V battery with you, that would be your best course of action.
Hope this helps,