Seleccionar registos aleatorios MySQL

RAND() numa cláusula WHERE será reavaliado sempre que WHERE é executado:
SELECT * FROM tabela ORDER BY rand()