Creo que eso podria funcionar.. Pues se hace una consulta, luego hago un random que va desde 0 hasta el numero maximo de resultados, tomas los resultados y los guarda en $res y luego el numero aleatorio se lo pongo a $res y asi ya obtuve un aleatorio de la consulta..
Código PHP:
$query = mysql_query("SELECT * FROM PRODUCTOS");
$rd = rand(0,mysql_num_rows($query));
$res = mysql_fetch_array($query);
echo $res[$rd];
Si no es asi, por ahi va la idea.