Well, for this game at least. I awoke this morning all hyped for HG and SS coming out tomorrow when I realized, I had not found out who I would be using as HM slaves. I took about an hour this morning using Serebii's moveset calculator and found a set I think will work for almost everyone.
Furret: This is pretty straight-forward. You've just started your Pokemon journey, you take your first steps into the grass on route 29 and bam, Sentret. Raise it to level 15, and you'll have a Furret. Teach it Cut, Strength, and Rock Smash. You can also teach it Dig if you'd like.
Chinchou: This one's was a little more tricky to find, but I finally found a way to acquire it before you have to use any of the HM moves you will teach it. Once you get to Olivine City, obtain the Good Rod. Fly back to New Bark Town and fish in the waters to the right. It's finding rate is 7%, but it's worth the effort. Teach this Pokemon Surf, Whirlpool, Waterfall, and Flash.
Beedrill: If you must explore the Dark Cave as soon as possible, Beedrill may be your best choice. You can catch a Weedle as soon as you get to Route 30. Once you evolve it, you can teach it Cut, Flash, and Rock Smash.
Lapras: This goes along with Beedrill somewhat. You can find this Pokemon deep in the Union Cave. You can teach it Surf, Whirlpool, Waterfall, and Strength. The problem here is that you will have to teach another Pokemon Surf to get to it. Doesn't seem too convenient to me.
Pinsir: This one can go along side Chinchou, though I wouldn't recommend it. If you feel you must get Rock Climb early in the game, you can go to the bug catching contest on Tuesdays, Thursdays, or Saturdays, and catch one of these. You can teach it Cut, Strength, Rock Smash, and Rock Climb. The problem here is that you have to teach a different Pokemon Cut to get through the Ilex Forest. Again, not too convenient.
Sorry I did not include Fly, but there are very few Pokemon that can learn Fly along with multiple other HMs, and all of them would require you to trade to get early in the game. I hope this helps.