Zakładając że każdy rekord w bazie ma unikalny numer id, pobierasz największe id, losujesz liczbę z przedziału [0,max_id], pobierasz rekord o wylosowanym id, jeśli zostały zwrócone dane to koniec, jeśli nie to losujesz nową liczbę i pobierasz rekord z bazy, i tak aż trafisz na dane.
Tak na szybko, pewnie można lepiej