The two most obvious solutions to me are:
-
Use a capacitor to power the Arduino for a fraction of a second when power is lost, and add a mechanism to detect loss of incoming power. If you power a Uno from 12V via the barrel jack and you don't connect anything that takes much current to the +5V pin or the output pins, then a 2200uF capacitor connected between Vin and ground will power the Uno for about a quarter of a second, which is way more than you need to save important data to EEPROM. You can detect impending loss of power using an Arduino input pin.
-
Save data to EEPROM just occasionally, and use wear-levelling to lengthen the life of the EEPROM. For example, if your data along with a 1-bit flag fits in 8 bytes, and you have 1K of EEPROM available, then you can write a different 8 cells each time. When you reach the end of the 1K, you flip the flag and start from the beginning again. When reading the data back, you use the flag to find the most recent data. This increases the number of times you can save the data in this example from 100k to (1K/8) * 100K which is more than 12 million. If you save data to EEPROM once a minute, that gives you 22 years before you reach the 100K rated life.