Simipour, Basculin, Carracosta, and Beartic (I assume you wouldn't want to use Samurott as an HM Slave if you chose it as your starter.)
Simipour and Basculin get Cut, Surf, Waterfall, and Dive.
Carracosta gets Strength, Surf, Waterfall, Dive.
Beartic gets Strength, Cut, Surf, and Dive.
If you need a Pokemon with Fly, I would suggest either Braviary or Swanna for that role (Hydreigon gets Fly and two other HMs, but I don't think you'd want to waste it as an HM Slave).
Braviary gets Cut, Strength, and Fly.
Swanna gets Fly, Surf, and Dive.
You can get all these guys before the Elite 4, with Swanna, Carracosta, Simipour, and Basculin being obtained fairly early into the game (and Samurott being obtained at the start of the game).
It should also be noted that all the preevolutions of these Pokemon can be used as HM slaves, although note that the preevolutions of Samurott cannot learn Strength and the preevolution of Beartic cannot learn Dive. The preevolutions of Hydreigon are useless as HM Slaves, only learning Strength.
Also, Dive is obtained after the Elite 4.