These are my ideas:
Buggy
Male
Bug
Insect Badge
HM01 (Cut)
Lv.12 Ledyba, Lv.14 Butterfree
Divak
Male
Water
Aqua Badge
HM06 (Rock Smash)
Lv.18 Wailmer, Lv.20 Marshtomp
Roxie
Female
Rock
Sand Badge
HM04 (Strength)
Lv.23 Onix, Lv.23 Nosepass, Lv.25 Graveler
Vincent
Male
Grass
Wood Badge
HM02 (Fly)
Lv.28 Roserade, Lv.28 Leafeon, Lv.30 Victreebel
Texina
Female
Ground
Soil Badge
HM03 (Surf)
Lv.35 Wormadam Sand Cloak, Lv.35 Dugtrio, Lv.38 Rhyhorn
Telekinette
Female
Psychic
Mystic Badge
HM05 (Defog)
Lv.41 Kadabra, Lv.43 Giafarig, Lv.43 Mr.Mime, Lv.44 Alakazam
Luno
Male
Dark
Moon Badge
HM07 (Waterfall)
Lv.44 Mightyena, Lv.44 Sharpedo, Lv.46 Crawduant, Lv.47 Houndoom
Muscla
Female
Fighting
Bicep Badge
HM08 (Rock Climb)
Lv.49 Medicham, Lv.50 Machamp, Lv.50 Hitmonlee, Lv.51 Lucario
I have no gen V pokemon there, for obvious reasons. Please comment.
Buggy
Male
Bug
Insect Badge
HM01 (Cut)
Lv.12 Ledyba, Lv.14 Butterfree
Divak
Male
Water
Aqua Badge
HM06 (Rock Smash)
Lv.18 Wailmer, Lv.20 Marshtomp
Roxie
Female
Rock
Sand Badge
HM04 (Strength)
Lv.23 Onix, Lv.23 Nosepass, Lv.25 Graveler
Vincent
Male
Grass
Wood Badge
HM02 (Fly)
Lv.28 Roserade, Lv.28 Leafeon, Lv.30 Victreebel
Texina
Female
Ground
Soil Badge
HM03 (Surf)
Lv.35 Wormadam Sand Cloak, Lv.35 Dugtrio, Lv.38 Rhyhorn
Telekinette
Female
Psychic
Mystic Badge
HM05 (Defog)
Lv.41 Kadabra, Lv.43 Giafarig, Lv.43 Mr.Mime, Lv.44 Alakazam
Luno
Male
Dark
Moon Badge
HM07 (Waterfall)
Lv.44 Mightyena, Lv.44 Sharpedo, Lv.46 Crawduant, Lv.47 Houndoom
Muscla
Female
Fighting
Bicep Badge
HM08 (Rock Climb)
Lv.49 Medicham, Lv.50 Machamp, Lv.50 Hitmonlee, Lv.51 Lucario
I have no gen V pokemon there, for obvious reasons. Please comment.