I'd like to have both available. Most other music players provide an option to shuffle the current playlist (which rearranges all the songs in a random order, and stay in that order) And they provide a "random song" option where all the songs from your current playlist are played in a random order for ever.

VLC shuffles the playlist upon hitting the shuffle button and does not alter the order until shuffle is disabled and reenabled again. I'd like VLC to go through the whole playlist in a random order once, and when every song has been played instead of reusing the same pattern again, reshuffle.

Yeah, I guess it seems obvious to me that the right way to "shuffle a playlist" is to shuffle a playlist. Literally just take a list of songs, and Fisher-Yates shuffle the bugger; give the user exactly what the button claimed.