An important question here is: do these objects contain references to one another? If they do, you will have a very, very hard time trying to read the serialized objects out of sequence. Even if they don't contain such references to each other - there's a very high possibility this will never work. Your objects may well refer to
other objects which are shared. E.g. if you have a class with a
String field, and two instances of your class refer to the same String - you will have a very hard time reading the second instance unless you read the first instance first. Because the shared string will get serialized as part of the first instance, and the second instance will just serialize a reference to the first one. That's a rather imprecise description, and I'm not sure of all the details myself, but I think it's extremely unlikely you will be able to achieve what you're asking for. The object serialization protocol is very much designed for sequential access, period. Skipping steps is not really an option for objects which were all serialized together using the same ObjectOutputStream.
I think that by far, your best option is the one mentioned in the fourth paragraph of your first post here. Read the entire huge file once, and write a separate file for each object. Yes, it will take some time - but you only have to do it once. Then you never use the huge file again.
Note that if your objects do contain extensive references to each other (not just to a few small shared objects like Strings) then this option won't really work either, as trying to serialize one object will end up serializing them all. In which case forget about trying to write separate files - each one will be as big as the original. You will just have to read the entire file and keep everything in memory. Or find some other way of storing your data besides object serialization.