Allora, il problema e' proprio quello dell'eliminazione. potresti usare una query cosi':

$rows il totale dei record, poi:
$select = "SELECT * FROM tabella LIMIT RAND(0,$rows),1";

dimmi se funziona.