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.
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.