You could count the number of records using

  SELECT count(*) FROM table
[download]

Then you could pick a random number from 0..$n-1 - call it $rand and using the 2 paramter form of LIMIT select it, eg

  SELECT * FROM table ORDER BY id LIMIT $rand, 1
[download]

This should be very quick and efficient. You should ORDER BY the primary key probably for maximum speed (where it says id above).

This method has the advantage that it will work with a WHERE clause on the the SELECTs), eg WHERE setup=1 or something like that

This two parameter LIMIT might be MySQL specific I don't know (it doesn't say it is in the manual though)

Update: I tried this on a large MySQL table (with 100ish columns and 500,000ish rows). Leaving out ORDER BY made only a very small difference. The first SQL statement was instant. The second took 8 seconds varying by $rand so maybe it is doing a full table scan here :-(