>.>
I know how people hate HM moves and all. I kinda do too... but it's pretty much necessary for a RPG game.
Bibarel IS hard to train... but if you want good HM users, you don't even need to have a Bibarel. You can spread around the HMs with the team evenly. Fly, and Defog are pretty much unnecessary, although Defog will help a lot. If you want, you can have Rock Smash and Strength on a Machoke or a Graveler or something, Waterfall on Azumarill or Gyarados or Floatzel (trust me, Azumarill is NO pushover), and Surf on Empoleon or some other Water poke with a decent SpA. But there's no reason to call something cruddy.