How do you write to a free location on an external EEPROM?
You can divide EEPROM space into entries and provide each entry with a single "dirty" bit. You could use a separate byte to store it, or reuse a bit from a byte which is not completely used by your data.

Suppose you start with EEPROM willed with zeroes, and you decide that the first byte of each entry holds the "dirty" bit in the LSb. When you log coordinates the first time, you'll have:

 /---"dirty"
01 51 00 00 04 00 00
00 00 00 00 00 00 00
 \---"clean"
...
00 00 00 00 00 00 00


(of course, you don't have to store GPS coordinates as BCD, it's just an illustration).

Note that as you add entries, it's trivial to keep track of the last one: just check the entries in sequence until you find a "clean" one and go back one step. Also note that the first entry is always "dirty".

This will go on until all your entries are "dirty":

01 51 00 00 04 00 00
01 52 00 00 05 00 00
...
01 53 00 00 06 00 00


At this point (when you have to write new data but there are no "clean" entries), you start writing from the first entry again, inverting the value of the "dirty" bit:

 /---"dirty"
00 54 00 00 07 00 00
01 02 00 00 05 00 00
 \---"clean"
...
01 53 00 00 06 00 00


(remember that the first entry is always "dirty"? Thanks to this, it's possible to simply swap the values representing "dirty" and "clean" entries without actually erasing anything).

To sum up, the algorithm is:


read the "dirty" bit from the first entry
scan entries until the value of the "dirty" bit changes, or until you reach the end.
to read the last logged data, use the last "dirty" entry
to write new data, use the first "clean" entry. If there are no "clean" entries, start from the beginning, inverting the "dirty" bit.