Based on my parametric search, the ATTiny43U is probably the best processor for this. It operates .7v and 5.5v, and is one of the picopower processors (very low current)
The only real drawbacks are that it has only 256 bytes of RAM , so you may have to write assembly (your code is so simple, I don't think you would have trouble with that), and it doesn't come in a DIP package (but does come in a SOIC package.)
Also, as a tip, the slower your clock frequency, the less power the AVR will consume. And make use of the sleep() function as much as possible.
All in all, the Arduino core is not ideal for this application, really. You might use it for development, but for a final application, I would look at writing assembly code.