Well, the easiest: If you have a primary key, especially one that is auto_increment, then just pick a random number from 1 to MAX(PK) and then go get that one record. If you have any "holes" in the table (e.g., from deleted records), then just do this:
SELECT * FROM table WHERE PK >= (SELECT 1 + FLOOR( RAND() * MAX(PK) ) FROM table ) LIMIT 1
The more holes you have in the PK numbering, the less random the results will be.
Say you had PK values of 1,2,11,12. Since the numbers from 1 to 12 will be picked roughly equally by the random expression, that means that 11 will be the final result when the random choice is any value from 3 through 11. So 11 will occur 75% of the time as the choice! But if your "holes" are themselves reasonably randomly occurring within the full range of values, then the results will be reasonably random as well.