Embora pareça um pouco estranho, isso é o que pode ser feito para atingir o objetivo:
SELECT FLOOR(10000 + RAND() * 89999) AS random_number
FROM table
WHERE random_number NOT IN (SELECT unique_id FROM table)
LIMIT 1
Simplificando, ele gera N números aleatórios, onde N é a contagem de linhas da tabela, filtra os já presentes na tabela e limita o conjunto restante a um.
Pode ser um pouco lento em mesas grandes. Para acelerar as coisas, você pode criar uma visualização a partir desses ids exclusivos e usá-la em vez da instrução select aninhada.
EDIT:citações removidas
