Средства и методы разработки

Если прекратить мыслить в терминах битов и байтов, то и задачи такой, чтения по произвольному _адресу_, не встанет. А запись у него не по произвольному адресу, а скорей строго по кольцу. Для рандомного доступа можно пробежаться один раз по всему  списку (разумеется с пропусками, ибо в каждой записи хранится её размер, т.е. относительно быстро) и построить индекс. Если очень неймётся индекс в самом EEPROM хранить можно, хотя вряд ли нужно. И, наконец, если записи фиксированного размера, то ничто не мешает сериализовывать в этот фиксированный размер. Зато на выходе обычная C-структура, а не говнокод космического уровня.