EEPROM with high endurance
Another solution could be to use a microcontroller with non-volatile FRAM.  FRAM doesn't suffer from the same limitations on write cycles as EEPROM.

Some of the MSP430 products from TI are available with FRAM, here's a link to an application similar to what you describe:

MSP430 with FRAM save state on power failure

Here's the Wikipedia article on FRAM: FRAM