Note that the original question asked for post-game HM slaves. However, I decided to post a more general answer because this question is one of our top 100 most searched questions, and I highly doubt that 800 people per week are looking for post-game HM slaves.
Krabby is probably the best HM slave for most of the game. It can be caught without using any HMs (by using an old rod in Cherrygrove City), and it learns rock smash, cut, strength, surf, and whirlpool without evolving.
Farfetch'd is the only Pokemon that can be caught before defeating Chuck (on Routes 47 or 48 in the morning or daytime) and can learn fly and another HM without evolving. It's not that great, but you don't have many better options.
Krabby unfortunately can't learn waterfall. At this point in the game, your best option is probably Golduck, which can be found by surfing in Ilex forest and learns rock smash, strength, surf, waterfall, and rock climb.
Once you defeat Lance and reach the post-game (or the second half of the game), it's time to get yourself a real fly user. These are the only options that learn at least 3 other HMs without needing to evolve.
Lugia: Whirl Islands, can't learn cut and rock climb
Latias: roaming Kanto (HG), can't learn rock smash, strength, rock climb
Latios: roaming Kanto (SS), can't learn rock smash, strength, rock climb
The best Pokemon to use with any of these fly users is probably Lickitung, which can be caught on Route 44 and learns cut, rock smash, strength, and rock climb (and surf and whirlpool, but the 3 fly users learn them too).
source
source
source
Of course, if you want to ignore all of this math, you can just use 2 Smeargles. You'll want heart scales to re-learn sketch after sketching each move, and I think the fastest way to get them is by smashing rocks in Violet City or Tohjo Falls.
