The other answer mentioned some general ideas; here are a couple of more-specific notes.
• You can direct your writes of single bytes through a routine that reads the EEPROM cell before writing to it, and if its value isn't changing, doesn't write.
• For load-leveling, you can divide the EEPROM address space into k buckets, where k =⌊E/(n+1)⌋, with n = data array size and E = EEPROM size. Initialize a directory, an array of m bytes all set to k, with m = E-n·k. When your device starts up, it reads through the directory until it finds current entry, a byte not equal to k. [If all directory entries equal k, initialize the first to 0, and go on from there.] If the current directory entry contains j, then bucket j contains current data. When you need to write new data, you store j+1 into the current directory entry; if that makes it equal to k, initialize the next directory entry to 0, and go on from there. Note that directory bytes get about the same amount of wear as bucket bytes because 2·k > m ≥ k.