I really need to know why ENUM or SET are bad options... Do you have the ability to explain farther why they are a bad choice? In the book I see Larry use it for male or female, but then again, those won't ever change, or anything.
For your 4th option, do you mean like this?
Song table - song ID, name, genre.
genre table - genre name
song genres table - Song ID, Genre ID.
to allow for a main genre and also some extras? if not can you clarify?