En Mysql dispones de la función RAND() y LIMIT .. una para seleccionar aleatoriamente y la otra para limitar .. si las combinas:
SELECT * FROM tabla ORDER BY RAND() LIMIT 4
http://dev.mysql.com/doc/mysql/en/SELECT.html http://dev.mysql.com/doc/mysql/en/Ma...functions.html
Con eso obtendras tus N registros aleatorios .. trabaja la consulta como si de un "SELECT * FROM tabla" se tratase como ya lo harás habitualmente.
Un saludo,