You can store the value distributed (as the XOR of all the values in the EEPROM).
Then you don't need any available flags or whatever and thus no need to write anything but a single entry. You simply step linearly round the EEPROM while the code is running to write each value (as the XOR of new and prev and existing location). At bootup you have to pick a random starting point (for wear to be level on average if the runs are short), as well as compute the total XOR of the EEPROM so you know the previous value written as each new write has to have the XOR of the new and previous values.
You can partition the EEPROM into multiple sections if you have multiple variables (those written more often would want more addresses to share the wear evenly).
The previous methods write twice as often as this scheme so it should double the life of the EEPROM.