Set "Options > General > Behaviour > Remove files from Playing Now after they are played".
You should probably also set "Options > Audio > Advanced > Advance to the next track when stopping after the current track" so that MC advances to the next track, and deletes the played track from the Playlist.
Select a View that shows all your tracks.
Shuffle.
Save the contents of the View as a Playlist.
Done.
As you play the Playlist, tracks will be removed from Playing Now, leaving only unplayed tracks.
MC will save Playing Now in the "Recent Playing Now's" Playlist Group when you stop playback and start it again, and at other times. You might want to research that and understand when it does save one of those lists. You could just start playing the most recent Playlist in that group later, but the saving of the recents is a bit hit and miss in terms of reliably recording your last position. So you probably should select everything left in Playing Now and save it as a new Playlist, or to an "In process" Playlist, whenever you finish a listening session, so you know you have a Playlist saving where you are up to. Perhaps, as Jim suggests, save it to a Car Radio button, so the "In Process" Playlist is always in the same location and easy to find.
Or if you never clear the playlist, just start playing Playing Now again later, with the remaining tracks. As long as you don't have "Options > General > Advanced > Clear Playing Now on exit" checked, Playing Now will persist between restarts.
Of course, you could also just set up a Smartlist that makes use of the [Last Played] field, to play only files that haven't been played for a while. But that wouldn't do exactly what you described.