Antes que nada has de saber el género y categoría de la canción anterior. Para ello has de seleccionar tambien estos valores en tu consulta.
Se me ocurre que podrías guardar esta información en dos campos de la tabla con un insert. Podrías hacerlo colocando una bandera (un 1 por ejemplo) que al cabo de un número determinado de consultas a la tabla desapareciera.
Al hacer la consulta añades la condición de que $genero y $categoria sean distintas de 1.
Código PHP:
$num = rand(1,50);
$sql = "SELECT * FROM `canciones` WHERE `id` = '$num' and '$genero' != '1' and '$categoria' != '1' LIMIT 1";
Creo que la solución va por ahí.
Saludos