Um ótimo post tratando de vários casos, desde simples, a lacunas, até não uniformes com lacunas.
http://jan.kneschke.de/projects/mysql/order- by-rand/
Para o caso mais geral, aqui está como você faz isso:
SELECT name
FROM random AS r1 JOIN
(SELECT CEIL(RAND() *
(SELECT MAX(id)
FROM random)) AS id)
AS r2
WHERE r1.id >= r2.id
ORDER BY r1.id ASC
LIMIT 1
Isso supõe que a distribuição de ids é igual e que pode haver lacunas na lista de ids. Veja o artigo para exemplos mais avançados