Looked into this and found a solution – sort of.
The best I can do for now is this:
1. You enable pagination
2. You set the order to Random
This will display your posts randomly, and allow pagination to work without duplicating posts.
However, your posts won’t randomize every time you reload now until the PHP session expires and is reloaded.
So the random ordering works on the first load, and then that order is saved.
Not perfect, but I figure it’s better than duplicating posts until a better solution is found.