Pues con php podrías ir guardando lo IDs que ya salieron y simplemente negarlos en la consulta.
No se si realmente funcione, pues como te digo es tema de SQL.
Cita: WHERE id NOT IN(1,2,3) ORDER BY RAND()
Suponiendo que los ID 1, 2, 3 son los que ya salieron antes.