Возможно ли создавать поток с произвольным доступом как в RandomAccessFile и с возможностью сохранения объектов как в ObjectOutputStream?

Реализовать такое конечно возможно, но могут быть трудности.
Если держать все объекты в памяти то проблем нет. А вот если нет, то придется заниматься распределением пространства в файле. Т.е. реализовывать механизмы наподобие тех, что используются в СУБД или файловых системах. И это уже не тривиальная задача.

Вопрос на засыпку. А зачем?

Учень удобно исползовать seek(int), в зависимости от задачи можно сильно во времени выиграть

тогда храните просто в массиве   

Как я понял, проблема в хранении на диске, т.к. объекты требуют много памяти.

тогда чем RandomAccessFile не подходит? одна строка - один обьект. 

Строка чего? Сериализованные объекты Java - суть бинарные последовательности. Если наперед знать смещение и длину каждого объекта в файле, то да, можно поколдовать с преобразованиями между ObjectInputStream и RandomAccessFile и сделать так, чтобы при чтении объекта его двоичное представление мапилось на соответствующий участок в файле. Но тут сразу возникает масса вопросов:

• в каком формате хранить смещения?
• сколько места оставить под каталог? что если все это место когда-нибудь заполнится?
• по какому признаку идентифицировать копию объекта (грубо говоря, что считать за имя)? 
• что если объект подлежит перезаписи, а в свою старую область уже не влезает? оставлять дырку? вести учет свободных дырок для переиспользования под объекты меньшего размера?

Короче, если хорошенько порассуждать над этими вещами, то очень быстро станет ясно, что речь идет о написании самодельной объектной базы данных. Спрашивается, нафига в таком случае изобретать свой собственный, когда уже есть куча готовых велосипедов?

Именно к этой мысли я и хотел подвести автора.