EEPROM byte/bit-wise writing without erasing possible?

Back to the original question:
Is bitwise deletion possible?

After studying the datasheet of the 24c32 that is coming with my RTC module the answer is: No

It only supports byte-write or page-write meaning 32 bytes in one of the 256 pages.

Regarding space management:
Since it's an odometer and values should only go up, it should be quite simple.

What about this simpler method:
(the example shows 4 pages with 1 byte each, but can be scaled to 256 pages of 32 bytes easily)

1. initialization: write odometer value to first page, set rest to 0: [ 1, 0, 0, 0 ]
   
2. current element: is the one with the highest number (the last one written)
   
3. write new value: a) find current element, move one page forward (wrap around the ends like a ring buffer), write new value to that element: [1, 2, 0, 0]
   
   

Next iterations: [1, 2, 3, 0] [1, 2, 3, 4], [5, 2, 3, 4] etc...

This way wear is spread across all pages evenly, there is no need of any extra space management structure.
Since the highest value marks the current element there can be a payload with history data just after the actual odometer value:
[ [1, p], [2, p], [3, p], ...]

Also writing can be reduced to something like: once every N minutes or K kilometers, whichever comes first.
If there is a power fail, only the last N minutes or K kilometers are lost.

The datasheet for 24C32 states 1,000,000 write cycles endurance - so without any levelling and writing every minute or km that would be 1000000 km (which is more than enough) or 694 days, nearly 2 years of non-stop riding.
Spreading this over 256 pages should multiply these values by 256 and keep me on the safe side...