Need a processor to be able to turn off its own power
Even though this has a lot of steps, it's still an outline.  You need to go through the circuit very carefully and make sure you're not accidentally powering a gate or the processor through an input pin -- so you need to insure that all pins are undriven, or driven to ground, when the processor is off.


Find a really low-power CMOS single-gate logic family that's compatible with your battery and input voltage (HCT may be more than good enough).
Power it from some "always on" supply (like the battery).
Run the +5V and a GPIO from your processor into a NOR gate.  Make sure the GPIO is pulled down when the processor is off.
Drive your "enable power" signal from the NOR gate
Run +5V to some other non-inverting gate (so it'll be LOW with no +5V, even when the micro power is off)
On reset, set the power enable GPIO high (to enable power).
When you detect that +5V is off and you want to turn off, set your GPIO low.