Random item from iterator?

I have the following code

number_list = (i for i in range(5))
permutations = (num for num in itertools.product(number_list, repeat=9))

This is generating an iterator called permutations which will hold all permutations of 9 characters within the number_list if I'm not mistaken. This can get pretty large for a big number_list.

I can iterate through permutations with next(permutations) but the problem is that it's sequencial. I would like to be able to draw a random item from any part of the iterator. If it was a list, I could simply do random.choice() but for a big number_list I don't have near enough memory nor time for that.

I could also just use next() and store a list of X amount of items and them randomize them but that won't work either because it can get so incredibly big that the outputs would be so similar it wouldn't really be "random".

I was wondering, if it isn't possible to draw a random item from the iterator, is there an algorithm which allows me to create an iterator which will output a random set with next() but that when it ends it will have gone through the entire permutations witout repeating?

The final idea would be having an iterator that would spit a random permutation of n characters out of a list of i elements, being able to get both n and i to arbitrarily large numbers without memory constraints, making sure that when the whole iterator ends up finishing (doesn't matter when, even if it finished after years in theory), all possible permutations would be exhausted without repetitions.