Ajax - Lazy load random elements without repeating

Ajax - Lazy load random elements without repeating

I have a database of, lets say 10,000 records. I have a webpage where I
want to display each record in a list, in random order. Because there are
so many records, I want to initially load only 100 records on the page,
and as you get to the bottom of the page, another 100 is added via AJAX,
then as you scroll to the bottom, 100 more, etc...
The trick is that overall, I want the order of the displayed records to be
random, but also, they cannot repeat. So just doing an AJAX call to pull
in 100 random records isn't going to work since some of those records may
have already been displayed on the page.
Is there a certain trick to doing this?
I was thinking maybe keeping track of the record id's that have been
displayed already and sending this in the AJAX call and then fetch 100
random records who's ID's have not already been displayed... But I'm
afraid for a high traffic website, this would get pretty slow as you can't
cache that too easily, without recreating the same thing using cached
arrays.
What is the best approach to this?