EEPROM Fatigue - Does it affect only the cells being written excessively, or will it cause global failures?
EEPROMs don't wear out from writing, they wear out from erasing.  If you look at the datasheet you'll notice that it states erase cycles.
Erase operations are block based. So an entire block of data is erased at once.  And in your case you can do this at least 10k times to each block.
Your idea can work, but any wear leveling algorithm needs to be block based, otherwise it will not provide additional life to the chip.
Also, in my experience, that number in the datasheet is fairly conservative in order to guarantee coverage under all temperature extremes.  So at relatively modest temperatures (close to ambient) you may get many more cycles.  In one chip that we had this issue with, it was specified at 50k cycles, but we routinely got close to 300k before issues arose.
And finally, as part of your algorithm, after you erase the block, do a check to make sure all bits were reset.  If not, then erase again (up to two times).  We found that this greatly extended the useful life of the flash, as the failure mode is not hard, but more of a soft curve.
If you want to avoid all the extra algorithm stuff, you can usually find an FRAM chip that is a drop in replacement for most EEPROMs.  They do not have the same wearout mechanism and can be erased/written 1 Trillion times typical.