I had a quick look at the ATM168 datasheet and not only does it support several decent power saving modes it also supports interrupt on any transition for certain pins whilst in a low power state.
You will have to write an interrupt handler but that need not be a very complex one just something that does whatever you want to do and returns to sleep mode again. You might need to deal with the situation where the down transition occurs whilst you are processing the up transition or vice-versa (but that would be a problem for a hardware one shot too).
So long as you keep the overall power consumption under 5uA you will find that in service battery life pretty much depends on ambient temperature and how badly stored the battery was before you bought it.