Le due cose sono leggermente distaccate.
Il player video è lo strumento che permette la riproduzione di un video, dato il percorso del file. Questa funzionalità è realizzata dal tag <video> di html5 che è supportato solo dai browser più recenti (Chrome 3+, Firefox 3.5+, Internet Explorer 9+, Opera 10, Safari 3.2+). L'alternativa è quella di usare un player realizzato in flash.
La playlist, invece, è un componente addizionale del player che gestisce l'ordine di riproduzione (appunto
playlist) dei video. Il tag <video> non consente l'utilizzo di una playlist, per i player realizzati in flash, dipende dalle scelte implementative.
Come soluzione al tuo problema dovresti usare un codice che carichi la sorgente del video in modo casuale.
Ad esempio potresti rendere l'intera pagina dinamica (usando un linguaggio come PHP o ASP o JSP) scrivendo l'url del video dopo una estrazione casuale.
<?php
// Array contente gli URL dei video
$video_src = array("url1.ext",
"url2.ext",
"url3.ext");
// Estrazione casuale
$i = mt_rand(0, count($video_src)-1);
// Stampo il codice nella pagina
echo "<video src=\"".$video_src[$i]."\"></video>";
?>
Una alternativa è usare un codice javascript (script client-side, quindi nel codice sarebbero visibili tutte le possibili risorse video).