Would it be possible to use some SRAM with a backup battery
Yes, Dallas even makes this a a unit.

Be careful, however, you will need a two stage supervisor circuit (or 2 supervisors with different cutoff points) and have the higher cutoff make the uC "shut up" and the lower cut the chip enable and write signals to the battery backed SRAM.

The reason is that if the SRAM is cut off while the uC is still running you might get a write pulse out of spec, so the UC must be shut off before the SRAM is shut down. The second shutoff is to avoid the SRAM getting extraneous signals during power up/power down. Also, it is advisable to use a 3.3 to 5 V rated uC to ensure that the uC does not do "strange things" during the window between the two resets.

Another approach is to forget all I stated above, write everything 3 times and on power up use whatever is identical in two reads.

Erik