If you're willing to add a column to your table you could use this approach:

Add a column to your table, I'm gonna call mine FOO in this example. Index FOO. You could do this with any type of value (integer, varchar, float/real, etc..). Assign every record currently in the table a "random" value within a range (say you decided that foo was a CHAR(10) you could assign it values from 'aaaaaaaaaa' to 'zzzzzzzzzz'). Whenevere you insert a new row into the DB assign it a random value in FOO as well.

Now whenever you want a random record just generate a random seed (using the same range and algorithm you used to seed the table originally) then select * from BAR where FOO >= '$seed'. Don't fetch back all the rows (you could use LIMIT if your dialect of SQL supports it). Fetch them rows from the query back one-at-a-time while FOO has a constant value. If you got back only 1 row, then you have your match. If you got back multiple rows then pick randomly among them.

If you do not pick an apropriate size for FOO and a valid randomizing function and your table grows much larger than expected this could become inefficient. But it should work good in some circumstances.