100k EEPROM writes "per bit" or as a whole?
It's not just write cycles that's specified, but erase/write cycles. On the AVR EEPROM can be erased by byte. Erasing sets all bits to 1, writing selectively clears bits. You can't program a 1, just 0s. If you want to set at least one bit to 1 you have to erase that byte.
Erasing removes the charges from the FET's floating gate, but on each erase cycle some of the charge remains on the floating gate, which won't be removed through the quantum tunneling. This charges accumulates and after a number of cycles there's so much charge left on the floating gate that the bit still will read 0 after erasure. That's what determines EEPROM life, it's erasure rather than writing. So you can safely write additional 0s, as long as you don't erase.
As a result, if the datasheet specifies 100k erase/write cycles you can have maximum 800k write cycles, one bit at a time, for 100k erasures.  

If you're using only part of the EEPROM memory space you can extend its life by distributing the data, like Matt says this is called wear leveling.
The simplest method of wear leveling when writing blocks of data is to include a counter with the data. Suppose you need to keep 14 bytes of data. Add a 17-bit counter as two bytes, you probably have a bit to spare for the 17th bit. Increment the counter before writing the block of 16 bytes. If the counter has reached 100 000 you know this block is becoming unreliable, so you move to the next 16 bytes. Use this until it is worn as well. And so on. A 4k memory consists of 256 sixteen byte blocks, so you can extend the original 100k cycles to 25 million.
It should be obvious that your gain is greater with smaller blocks of data.

further reading
data retention on a microcontroller