Código:
SELECT * FROM tabla ORDER BY Rand() LIMIT 10
el LIMIT 10 es el numero de filas que te devuelve.
Esto ordena la lista aleatoriamente, pero no te puede garantizar que las primeras 10 veces que se cargue la pagina el primer registro fuese diferente.
Para eso deberias usas sesiones, y el fin creo que no lo justifica.
Igual esto lo restondi aqui:
http://www.forosdelweb.com/showthrea...light=sesiones
Seria fácil de adaptar si creas un array con los resultados de la bd.
Saludos.