I'm trying to think how to do it. My thinking at the moment consists of the following three alternatives:
1) select random lines that ignore the criteria, then discard those that do not match at the application level, and select more random lines if necessary. This method will be effective if your criteria match a large number of rows in your table, possibly 20% or more (you need to check)
2) select the lines of the following criteria and select the line based on a random number between 1 and the counter (*) (random number defined in the application). This will be effective if the data matching the criteria is evenly distributed, but it will be terribly bad if, for example, you select a date range, and most random numbers will fall on records outside this range.
3) my current favorite, but also the most difficult. For each combination of criteria that you are going to use to select a random record, you insert a record in a special table for these criteria. Then you select random records from a special table and execute them back to your data. For example, you might have a table like this:
Cat table: name, age, eye_colour, fur_type
If you want to choose random cats with brown fur, you will need a table:
Table cats_with_brown_fur: id (autonumber), cat_fk
Then you can select a random record from this table based on the autonumber identifier, and it will be fast and will produce evenly distributed random results. But really, if you choose from a variety of sets of criteria, you will have some overhead for maintaining these tables.
What my current take on, anyway. Good luck.