You can do that right now pretty easily using playlist properties on the player.

Create a new playlist called "Random by playlist", tag it as "always randomize contents", and then copy all your other playlists into it. It will do exactly what you just said when you play it (with shuffle turned off).