Me gustaría seleccionar un video de YouTube al azar de la base de datos MySQL y mostrarlo en mi página web

Parece que están desaprobando las llamadas mysql y recomiendan usar las llamadas orientadas a objetos mysqli en su lugar.

http://us3.php.net/manual/en/function .mysql-connect.php

<?php
    $mysqli = new mysqli("host", "username", "password", "database name");
    if ($mysqli->connect_errno) {
        echo "Failed to connect to MySQL: (" . $mysqli->connect_errno . ") " . $mysqli->connect_error;
    }
    echo $mysqli->host_info . "\n";

    $res = $mysqli->query("SELECT EmbedURL FROM `Videos` ORDER BY RAND() LIMIT 1");
    $row = $res->fetch_assoc();
?>            

<iframe width="560" height="315" src="<?php echo $row['EmbedURL']; ?>" frameborder="0" allowfullscreen></iframe>

<p><?php echo $row['EmbedURL'];?></p>

Esto funcionó para mí en mi servidor local que ejecuta php 5.4. El primer comentario sobre el constructor recomienda usar un conjunto diferente de comandos si está usando una versión de php anterior a la 5.2.9.