1. Yes, their pokemon change, as, by your post, you have already discovered.
2. Capture a Hoppip. It evolves into Skiploom, then Jumpluff.(not sure on that spelling). It's Grass/Flying, so Pryce WILL murder it, but it's cool. Chikorita's also good, and if you capture a Gloom on Route 48, then you can get either Vileplume or Bellossom, the latter of which I find adorable.
3. Put him to sleep, do what you've done, and get something with False Swipe aswell. That way it can be at 1hp, sleeping. That's the best you can do.
You can also get Timer Balls, which I'm sure you can get somewhere.....so if it drags on for about 40 turns, you can use them and they'll be really good. If you have a lv.100, once you've put it to sleep and weakened it, send that out, and Level Balls would work well. I think Heavy Balls generally work on legendaries too.