Two points I didn't see here:
EEPROM is guaranteed for 100k writes per address. It will last much longer, and I have seen tests where they wrote 1 millions + times to the same address.
You can also increase that life even further with some wear leveling techniques.
In one project i worked on we needed a long term counter (think hour-meter) so for wear leveling i wrote the value to 1 of 10 addresses randomly. Then simply read all the address and pick the biggest number. Vola, 10x on your eeprom life.
Secondly whats wrong with SPI flash memory?
64Mb / 8MB flash chips are a dime a dozen commonly used for bootloaders and such. Can be had in all form factors too. Adesto Technologies is my preferred brand 