I also think that shooting over cranked on a hvx and having your talent play the track extra slow seems like your best bet.
I shot a 35mm music video in film school that was the exact mirror of what you should do. I shot at 48fps and re-recorded the song twice as fast but kept the pitch the same. Make sure your band has lots of time to practice playing along with the song at the new speed (as you are undercranking it is probably a lot easier that playing a song faster and overcranking). My project ended up working perfectly, the timing of mouth movement lined up perfectly with the song (not that i could not adjust that in post).
So the final effect i got, was a band playing a song and visually their movements were in slow motion, altho the song was still being preformed at its normal speed (thank you Spike Jonze for the idea, from your music video of Weezer - Undone).
So back to your music video, I recommend the HVX if youir going HD as its variable frame rates are perfect for your project. As you are undercranking as opposed to my project where i overcranked you could easily use a dv camera (try to get one with progressive scan). If you would have to rent a dv camera anyway, go for the hvx instead, as it is not that much more $. If you decide to go the dv route just shoot the project on progrssive mode at 30fps and then just speed up the clip as you like in post.
Good luck with you shoot
Julian