... if you don't have a battery or a big big capacitor ("supercap") or some other source of backup power - depending on the time you want to back up - the only choice is a dedicated nonvolatile memory.

Besides standard EEPROMs, which have relatively low endurance, so if you need to update the counter often you might run out of the reliable number of cycles (sometimes cunning schemes are deviced utilising multiple positions in a bigger EEPROM to achieve longer lifetime); I would like to direct your attention to RAMTRON's FRAM devices, with virtually (or in the case of 3V devices, literally) unlimited cycle number, although at a higher cost of the device.

JW