What you need is a technique called **wear leveling**. It doesn't write your data every time at the same location in the EEPROM, but uses some algorithm to use different locations. I've read about complex wear leveling algorithms, but I wouldn't know why the following simple method wouldn't work.  

Add to your data a 24-bit counter, so that your data block is for instance 8 bytes long. A 64kb EEPROM can then hold 1024 blocks.  
Look at the counter of the first block. If it's zero you used the maximum number of write cycles for that block, so you move on to the next block and check that counter. Repeat until you find a counter > zero. That's the block you're currently using. Microchip's EEPROMs have a 1 million cycles endurance, which you can increase to a billion with the given example of 8 bytes per block in a 64kb EEPROM. That should be enough to outlast your product: 31 years if you write once every second.  

You'll want to initialize your EEPROM on first use. How do you know when that is. Use tha last 8 byte block to write a unique signature upon initialization. Check at each power-up if the signature is there. If it isn't the device has to be initialized. You can preset the counter in each block with 0xF4240 (for 1 million) or clear everything to 0xFF and write the 0xF4240 when you first use the block.  
Initializing an EEPROM is needed because sometimes a certain pattern is written to it in the production process.

**further reading**  
[datasheet 24AA64](http://ww1.microchip.com/downloads/en/DeviceDoc/21189S.pdf)  
[EEPROM Endurance Tutorial](http://ww1.microchip.com/downloads/en/appnotes/01019A.pdf)