If a data structure can be arbitrarily long, this implies some kind of a data structure involving a linked list to avoid wasting memory. Unfortunately, it really is a bare-bones linked list, which means that we don't know the length until we traverse it.
What would we have done if we knew the length? We could pick a random number between 1 and the length, and then traverse that many items to get to our random item. Since we don't know the length, it means the question is, how will you know where to stop?
Constant growth for storage means you start with a fixed number of slots (lets call this number X) and keep them through the process. You could put items into these X slots, such as one out of every ten that you pass. That would mean you could pick items by rolling a 10-sided dice that shows a 10, and put them into one of the slots.
A problem is that you would have to remove past randomly-selected numbers to make room for new ones, and you would be biased towards items that appear later in the series. This would not be random.
And what about a string one character long (in this case, we can pretend we had been given an array, a string, a queue, or whatever) ? What if, at the start, we always select the first item to be the random choice? That would mean that an abrupt stop would give us the correct answer for a length of one. Another interesting thing is that we can store item one into a single container, instead of needing X (where X is a constant) slots.
What about two? Well, we would compare the container with item two and decide that the random choice for the container should be either what it already contains (item one) or item two, with a 50/50 split. Great! So our algorithm works for a length of one as well as two.
This is starting to feel like we've established a base case (what happens when the list has only one item?). We may be on track to show that constantly looking at the next item and comparing it to the one in the container may just work. If so, we could have a proof by induction.
So if we were at item three where the whole list is only three items long, then a random generator would have picked it with a probability of 1/3. So if we're comparing item three to whatever is in the container, then if a 3-sided dice rolls a 1, we can set container to be item three. That works. But what about the other 2/3 chance, where it could be item one or two? In that 2/3 chance, we pick the container. The container contains only one item (the first or the second, whichever one won the first coin flip previously.) For this to be a valid idea, both item one and item two should have had a fair chance to be in the container currently with a 50/50 split, correct? And we know that it was.
So when we come to item four, we replace the container with item four with a probability of 1/4, or use the value in the container with probability of 3/4 (e.g. 1-1/4 = 3/4, or the rest of the time.) The point is that at each step, the container contains the random value of the previous n-1 number of items.