Depending on your clock speed, you can run as low as ~2V. The microcontroller will also use far less current at low clock speeds. See the datasheet for more exact numbers, there will be a chart for the clock speed and minimum required voltage to operate. The current consumed can be calculated per Megahertz, but may also not be linear. Higher clock speeds (16-20Mhz) will consume far more than 8Mhz, and the difference is not linear.
Your microcontroller will not consume more than ~50mA (this is what an Atmega328P at 16Mhz uses). If it's consuming 500mA you are doing something horribly wrong, and probably a short circuit somewhere.
If you put 2 AA batteries in series, run at 8Mhz internal clock, you should get about 300-500 hours of run time. This is about 2-3 weeks of constant operation, not considering any other circuit losses or silliness.
Also the capacity of a battery written in Amp-hours (or Milliamp-hours) does not really relate to it's ability to source current. Internal resistances and different battery chemistry will determine it's current output and how much the voltage sags under load too. For example I have a little 260mAh lithium ion 3.7V battery that can pump out 5 Amps if it wanted to - but this is not good for it ;)
Your AA batteries, and batteries like the standard 9V "transistor" battery have terrible current output capability which newcomers to Electrical Engineering often don't know. You would be lucky to get a few hundred milliamp out of a standard (NiMH) AA battery. More in parallel will give more current output, and more capacity, but obviously only as much voltage as a single one.