How about using a rechargeable battery pack?
When the power is on charge the batteries and run the processor - when the power goes off disable any outputs or anything that takes much power and have a single LED to indicate that the power is off but your processor is fine
Can't remember if an Arduino has a "sleep" function - but it does not take much battery to keep the standard processor running for a long time