select key from (select key, count(1) 'seq' from table)
where seq = $RAND
or the equivalent using temporary tables. It's what
databases do, so it will suck to build the temp table
for large databases. If you can get the DBA to add a
sequence number, then use that instead of the temp table.
If your sequence number can have holes, then get the
first record where seq >= $RAND. That's assuming your
holes have even distribution also.
barring that, I see no alternative to reading a cursor
until your number is up (from a 'select key, count(1)
from table' query. Do a 'select count(1) from table'
to determine the number of records in the table.
BTW, reading from the cursor until you get to the record
you want (i.e. a sequential search) happens all the time
in SQL. Its just called a 'table scan' instead, and
happens when there's not an available index to locate
matching records for a where clause.