I did this once using a combination of programs, but mostly Nero Vision. Nero has a great tool to edit clips out of movies and export them (I first used a program called Super to encode into .avi, which can also remove the original sound). I did up a copy of the song I wanted to use with Audacity, and then used Nero Vision again to combine the audio and video clips.
It is probably possible to this all in one program, but that is the way I did it and it worked quite well.