These are all good suggestions for writing an EEPROM. Back in the day, a lot of flip phones used to write the eprom every time you closed the lid.
Another possibility, though, is to use a different memory technology. There are memories that do not have a wear mechanism, so you can write them constantly. The first one is plain old static ram. Many PIC processors are so incredibly low powered in sleep that the main register memory can easily be made non-volatable with a coin cell or super cap.
Or, many real time clock chips have a little bit of RAM and they are intended to run on minimal standby power. If you don't need the clock function, you don't have to hook up a crystal, and then they take even less power. In this mode, the clock registers themselves can be used to store arbitrary data. Microchip MCP7940 is a classic in this category. It has 64 bytes of RAM not counting the clock registers.
Ferroelectric RAM, aka FRAM, is non-volatile without any power at all. The only slightly suboptimal thing about FRAM is that the read is destructive. Doesn't sound like that would matter in your application. These are pricey on a per-byte basis but there are sub-kbyte parts around 50 cents that can be cheaper overall than anything requiring a battery or a supercap.
The best is magnetoresistive RAM, sometimes called MRAM. This is a fantastic technology. You could write every millisecond for thousands of years without wearing it out. The read is non-destructive. Sadly, where FRAM is "pricey," these are freakin' expensive.
Whatever the memory technology, it is a good idea to design in a little redundancy. You can set up multiple copies of the data and write them sequentially, so there is always at least one copy that is intact if the right cycle doesn't complete before power goes away.
I use multi-dimensional parity on my non volatile storage so I can recover from an interrupted write or other corruption. It's a little more complicated and takes a few more CPU cycles than multiple redundant blocks but gives you more protection with less extra storage.
I hope that was helpful to someone ...