Selecting all the records out of a database just to choose a random one will definitely have the DBA breathing down your neck. I haven't used mysql much, so I can't comment on the LIMIT parameter.
What you should do is find out which column on your table is the primary key. If there is no primary key then you will need a unique column. Use this column to build a list, you could stuff it in an array if it's not too large. Pick a random number and look it up via the array. Now run your select against the table to return this row. It will be worlds faster.