To me "utility" or "slave" pokemon are "travel" pokemon. You only use them when you're going somewhere, right?
I have used Azumarill, Zigzagoon/Linoone, Geodude/Graveler, Dragonite, Lapras, Wailord, Tropius, Seaking, and a few others. I won't name the movesets because I don't think it necessary. (You can guess pretty easily what I had in mine based on what others said were in their "travel" Pokemon' movesets.)
Pokemon can be made to forget HMs by the Move Deleter.
I'm surprised that no one brought up anything about the pokemon that can learn FLY AND
because that's one thing that has ALWAYS bothered me - only being able to have a team of five pokemon. (Being ADD I must
have both moves available otherwise I'm constantly running to PCs so I can do something else
before I forget about it.) Those are the 2 HMs that are used most often
So here's a list of which pokemon can learn FLY AND
I'm not familiar with Diamond/Pearl so can't add any pokemon from that generation. Feel free to add to my list with DP pokemon or any pokemon from older generations that I missed.
Hope this helps someone.
These HMs are in order of how often I use them.
4. Rock Smash
4 1/2. Headbutt (for older generations)