I have had many bad experiences with batteries in these situations. The chargers add complexity and the batteries have a finite life that once expired brings all of the problems you are trying to solve right back at you. I have had batteries fail and take out the board by corrosion too.
Down the road the batteries fail then you have exactly the same problems until this is understood. Then you may need to send expensive service people out to change batteries in remote places just..because.
If you are trying to protect data integrity in a commercial/industrial setting then you need to do several things:
Determine if the information to be saved is a machine state that you want to return to.
Or
Is this information something like a user setting change.
If it is a user setting change it should be done once the <Enter> key is pressed. (Right then) as MikeHalloran pointed out.
You immediately write the info then you read it back and compare it with what you just wanted saved.
If this is important information you do this three times in three different locations!
When you read the data back for use,(next boot, etc.) you compare all three values. If they don't all agree, it is assumed the two that do are correct and the third is changed to agree. The prudent engineer then increments another nonvolatile register noting that there was a nonvolatile error.
If this is information is to save the process or machine state then the hardware must be designed to support this. You don't just assume you can "quick do it before the power is gone".
You store "some" energy somewhere to keep the system running long enough to write the data and read it back and re-write it if need be. In modern micro systems the amount of energy does not need to be very much at all. A 100uF is often more than enough. But the key is to make sure you only do the orderly shut down ONE TIME. Because if you don't then you may be caught with your pants down on subsequent shut downs. This is because the power often does not just go away... It almost goes away then returns then does go away but comes back briefly then goes away again. All in a few dozen line cycles. This will cause multiple "shut down storage attempts".
So as I stated above, all you need to do is provide enough high-side energy storage in the form of a capacitor to do a single orderly shut down. This also covers simply flipping the on/off switch.
Monitor the state of the high-side voltage. When the voltage drops to a point in a normal power switched-off situation where you would still have %250 of the time needed to preserve your states of interest you INTERRUPT your processor.
Proceed to save and check your data. Then lock the processor until proper voltage is available again. This can be done by your watch-dog although hardware comparators and timers are often used as can be seen by the 20-30 chips Maxim and others make for certifying supplies to processors.
As soon as power is restored run your system initialization, read back your info from three locations if that is the case and continue. Batteries need not apply..