Anche se sembra un po' imbarazzante, questo è ciò che si può fare per raggiungere l'obiettivo:
SELECT FLOOR(10000 + RAND() * 89999) AS random_number
FROM table
WHERE random_number NOT IN (SELECT unique_id FROM table)
LIMIT 1
In poche parole, genera N numeri casuali, dove N è il conteggio delle righe della tabella, filtra quelle già presenti nella tabella e limita il set rimanente a uno.
Potrebbe essere un po' lento su tavoli grandi. Per velocizzare le cose, puoi creare una vista da questi ID univoci e usarla al posto dell'istruzione select nidificata.
EDIT:virgolette rimosse
