I don't have HM slaves on purpose, I just end up eventually with Pokemon that know Strength, Cut, Rock Climb, and Fly (lol I don't really have a pokemon that knows all those)
In Gen III I have a Gyarados with the water-based HMs (except Dive, my Marshstomp knows that), and a Vigoroth for, well, the rest. I also have a Farfetch'd on my LG that knows Fly and Cut. Gen IV had the Shiny Gyarados, plus eventually my Feraligatr. My Darmanitan served as my manual laborer in Gen V, while my Stoutland Surfed me wherever I needed to go.