prova l'esempio che trovi sul manuale mysql...
codice:
LOCK TABLES foo READ;
SELECT FLOOR(RAND() * COUNT(*)) AS rand_row FROM foo;
SELECT * FROM foo LIMIT $rand_row, 1;
UNLOCK TABLES;
estrai rand_row e lo rilanci nel LIMIT della query successiva.