Not sure on AVR, but on some other EEPROM/EPROM/FLASH modules, the data can be overwritten when the bits goes in one direction. AFAIR, it was going 1 to 0, this way you can writes the 8 bits before moving to the next one. This has to be checked chip by chip.
This is explained here:
http://electronics.stackexchange.com/questions/21232/100k-eeprom-writes-per-bit-or-as-a-whole
and also have some suggestions to write the counter forward in the memory as it increase, distributing it on the whole chip area rather than in one location.
