Bibarel, Bidoof's Evolution, is generally considered to be the "perfect" HM-Slave(learns all HMs except Fly and Defog, which every Flying-type except Beutifly can learn as far as i know), if you don't have the impossible-to-get-outside-japan-Mew, which can learn every TM and HM there is, but if you actually manage to get a Mew, you'd proably make something better out of it than a HM-Slave "/
If you don't have a Generation IV Game, then a Tentacruel and Pelipper can learn every HM in Generation III.
Or, you can just hate Defog and try to get through the Foggy routes without it(it's not
that hard, you can still see pretty good), and try to put the HMs in use instead :)
A Fighting-type Pokémon can be useful with Rock Smash and Strength, as Rock Smash has a 50% chance of lowering your target's Defense, a chansey with Rock Smash and the Serene Grace ability(raises added-effect chance by 50%) would have a
100% chance of lowering your target's Defense, if it does not have the Clear Body ability.
A Floazel with its high Attack stat can use a STABed Waterfall quite powerfully, as it's Sp. Atk is much lower than the Attack, a Waterfall despite lacking 15 points power can hurt a lot more.
Fly is obliviously put on a Flying-type, and you can keep Cut on whatever Pokémon you'd like until you get to Canalave and don't need it anymore.