Arduino Standalone construction
That's actually quite an involved question to answer. The short answer is "Yes, you can do without the regulator as long as you get the voltage right".

And that is where it gets tricky.

The datasheet states:


  
  Operating Voltage:
  
  
  1.8 - 5.5V
  
  


So you can power it from two or three AA batteries, for instance (3V - 4.5V). However, that is not the whole story.

The voltage you provide it with dictates what frequency the chip can reliably run at. Later in the datasheet is this nice little graph:



Since the normal Uno-like arrangement runs at 16MHz you're looking at a minimum voltage of around 3.8V - 4V (it's actually quite hard to work out from that graph).

But if you are willing to reduce your clock speed to 8MHz (which is what the 3.3V Arduino "Pro" boards run at) then you can drop right down to about 2.5V.

At a 2.5V lower limit with 3 AA batteries it would equate to a minimum voltage of 0.83V per cell, which is below the normal minimum accepted "flat" voltage of 0.9V per cell. 

So powering from 3 AA batteries with a clock speed of no more than 8MHz would give you probably the best run-time.  Note, also, that a decrease in clock frequency decreases the current consumption as well - the slower you run the chip the less current it needs. You can see that in this graph in the datasheet:



And yes, as you can see, the lower the supply voltage the lower the current as well. So as the batteries run down and the voltage drops so does the current, reducing the speed at which the batteries will run down. 

As you can see, if you don't mind the supply voltage changing (which of course will affect everything else in the circuit, so you need to check those out first), running directly from batteries without a regulator can actually have advantages. But as I say, you need to check what else you are running in the circuit to make sure it doesn't mind if the power supply voltage drifts.

And don't forget, also, that the supply voltage affects the ADC readings, since they are referenced to that voltage as well.