Agregando a lo que Cluster acaba de responderte, tambien puedes ir guardando en una session, o cookie los ID's que van pasando y tu consulta podria quedarte como
Código PHP:
SELECT * FROM tabla WHERE id not in ($id_aleatorio_obtenido) LIMIT 1
con $id_aleatorio_obtenido = "N,N,N,N,N,N,N";
Por ejemplo:
$id_aleatorio_obtenido = "1,20,35,41,52,97,15,10"
Sugiero esto, por si tenemos 100 registros ordenados por ejemplo del 1 al 100 y en el primer random surge un 50, podras obtener aleatoriamente desde el registro numero 50 al 100 perdiendote de los 49 primeros, de esta forma puedes jugar con todos los registros que tengas, obviando los que ya hayas mostrado.
Saludos