A vector-like data structure with allocation table; O(1) indexing time required
The indexing time is always O(1) for an array whether you reallocate or not! Reallocating is not a bad idea if the table size doubles each time the array overflows, insertion takes constant time amortized.

Your idea is no different from a linked list of arrays of fixed size (correct if I'm wrong). If the list gets really large, looking for an element will take a lot of time.