Hola,
Usa esta SQL:
SELECT * FROM tabla ORDER BY RANDOM() LIMIT 1
con esto obtienes el primer registro (LIMIT 1) de la tabla cuyos registros han sido ordenados aleatoriamente (ORDER BY RANDOM()).
Y para redireccionar, usa el header("Location: url") (
www.php.net/header), poniendo detras exit;.
Saludos.