Da quello che ho capito ti serve estrarre un record in maniera random.
Esiste la funzione RAND() di mysql, ma non funziona molto bene.
La tua procedura potrebbe avere dei buchi, nel senso che se tra l'id max e il min hai cancellato qualche record, potrebbe cercarti proprio quello.