Du hast doch sicherlich eine Spannungsversorgung, die über den 5V für den AVR liegt.
Diese Spannung würde ich zu einem Komparator führen, der bei Unterschreitung an einem Eingang des AVR einen INT auslöst, wonach die Daten schnell noch im Eeprom gerettet werden.
Wenn Du also z.B. 12V hast, dann setz die Schaltschwelle z.B. auf 11...10V. Von 11...10V bis 8V (3V benötigt wahrscheinlich der Spannungsregler) ist noch genug Zeit, um die Daten zu retten. Wenn Du dann abschaltest, wird sich der Elko 'langsam' entladen und die Spannung auf 11...10V absinken.
Es gibt viele (Power-On-Reset-) Bausteine, die so was mit drin haben; Power-Fail ist der Begriff dafür; ich benutze den MAX 690. Der ist allerdings teuer, weil er als 3. auch noch einen WatchDog hat.