You must track the permutation you're stepping through.

E.g. you have 4 items. You shuffle them to get a random permutation:

4 2 1 3

Note: these are not indices, but identifiers. Let's say you go through the first two items:

4 2 <you're here> 1 3

And two new items arrive. You insert each item into a random position among the remaining items. E.g:

4 2 <you're here> 5 1 6 3

If items are to be deleted, there are two cases: either they have already been visited, in which case there's nothing to do, or they're in the remaining list, in which case you have to delete them from there.