Pues, por ejemplo metes la dirección de cada vídeo en un array:
$array[0]="http://..."
$array[1]="http://..."
etc.
creas un número aleatorio y lo usas como indice para seleccionar el video deseado.
$video_url=$array[rand(0,N)]
Despues solo te queda sustituir en el objeto <object> los sitios donde aparezca la dirección por tu variable $video_url
<object width="425" height="344">
<param name="movie" value="<?php echo $video_url ?&hl=en&fs=1>"&hl=en&fs=1"></param>
<param name="allowFullScreen" value="true">
etc.
Listo