I agree with Ken. His concern that deletes will cause trouble is pretty minor, and easily handled.

As Ken suggested, create a row id. Keep track of the maximum rowid, call it M. To get a random row, choose a random integer in 1..M and then select the corresponding row.

If you start deleting rows, then you'll have holes: the table will have N rows labeled 1..M, with N<M. In this case, choose your random int from 1..M and select the corresponding row. If there's no row there, just choose another random int and try again. This introduces no bias; the row eventually returned will be uniformly chosen from all the rows.

If N/M is large (near 1, few holes), this approach works fine.

When N/M degrades, you'll waste too much time shooting into holes. When N/M is unacceptably low (say less than .9), lock the table and reassign the rowids sequentially.