You're on the right track by associating songs with the various intervals. I covered this on the course I'm doing last year so I dug out the list from my folder (see below). Some of the songs I use are from my youth that we used to sing in church so you may or may not know them, but most are pretty generic. You can always go through 'classic' songs from your own music collection, work out the intervals, and compile a list that works for you...
b2 / b9 - Jaws, Killing In The Name Of
2 / 9 - God Save The Queen

b3 / #9 - Greensleeves, Castrol GTX advert (UK only!)
3 - Morning Has Broken, While Shepherds Watch Their Flocks
4 / 11 - Away In A Manger, Hallelujah
#4 / b5 / #11 - Simpsons, Maria
5 - Top Gun, Star Wars
#5 / b6 / b13 - The Entertainer, Close Every Door, Eminem (the bit you can hum from the video with the dancing Sadam)
6 / 13 - My Way, Jingle Bells (verse), My Bonnie Lies Over the Ocean
b7 - Star Trek, Milk Tray advert (might be showing my age here!)
7 - Superman
The best way I found to learn them was to record the various intervals and make individual mp3 files and then play them in WinAmp with shuffle on whilst looking away from the screen. Use the pause key or play-previous (z) while you work it out in your head and then look at the screen to confirm.
If it's any help you can download the mp3 files I used
here.
It's all about training, the more you practice the easier it will become.
Jon