Infernape, Roserade, Togekiss
— You can get Chimchar as a starter, which eventually evolves into Infernape
— You can also get Budew at a very early point, at Route 204 north of Jubilife City. You can level it up by battling Magikarps after obtaining the Old Rod to the west of Jubilife City, or catch it on the route east of Hearthome as a Roselia. By this point it should have learned decent grass moves.
— As for Togekiss, you receive a Togepi egg shortly after beating Gardenia in Eterna City. It will take some time to level it up and evolve it into a Togetic since you'd be forced to either level it up via Exp. Share or increase its friendship using the Soothe Bell that Cheryl gave you (assuming that your Budew already evolved into a Roselia, or you are planning to catch Roselia after defeating Fantina). It will also take some time before you get your first Shiny Stone in Iron Island, but I think having a Pokemon with Pickup (Pachirisu, Ambipom, Munchlax) would help you get Shiny Stone at a much earlier point in the game.
I also recommend evolving Togetic first with a Shiny Stone before Roselia, as Roselia learns a great move later in the game (Petal Dance).
Suggested Moves for Infernape:
Thunder Punch, Flare Blitz or Fire Punch or Flamethrower, Brick Break or Close Combat, and Shadow Claw
• Thunder Punch can be learned via Move Tutor west of Pastoria City
• Flare Blitz can be learned via level up, but at a late level. Fire Punch and Flamethrower are much more accessible early on. Fire Punch can also be learned via the same move tutor, and Flamethrower can be learned as a Monferno.
• Brick Break or Close Combat for STAB.
• Shadow Claw for Coverage against Psychic types
Suggested Item for Roserade: Persim Berry (always make your Roserade hold a Persim Berry!)
Suggested Moves for Roserade:
Petal Dance, Sludge Bomb, Shadow Ball, and Leech Seed [or any other move]
• Petal Dance can be learned by Roselia at lvl 40, so don't evolve your Roselia as soon as it evolves from Budew!
• Sludge Bomb for STAB, the TM can be get on the Galactic Veilstone HQ
• Shadow Ball for coverage against Psychic and Ghost types
• Leech Seed for healing, though you can swap it with any other moves you want
Suggested Ability for Togekiss: Serene Grace
Suggested Moveset for Togekiss:
Air Slash, Aura Sphere, Magical Leaf, Flamethrower
• Air Slash, STAB move and has a high flinch rate if used by a Togekiss with Serene Grace, can be learned via Move Remembered
• Aura Sphere, Coverage against Ice and Rock, can be learned via Move Rememberer
• Flamethrower and Magical Leaf can be replaced with any other moves you want, but Togetic can learn Magical Leaf via the Move Rememberer and Flamethrower can be get on Fuego Ironworks, located nearby Floaroma Town.
Gastrodon, Froslass, Magnezone or Drapion
— You can get Gastrodon as a Shellos in the Valley Windworks or the route east of Pastoria near its evolution level. East Sea and West Sea don't have any stat/ movepool differences so I recommend catching Shellos before you challenge Crasher Wake, since Shellos won't be able to do much help in Gardenia's gym.
— You can catch female Snorunt in the snowy routes before Snowpoint City (which won't be that hard because the gender ratios of Snorunts are 50% male/ 50% female). You can also get a Dawn Stone in Pastoria City using the Dowsing Machine.
— As for Magnezone, you can get it as a Magneton/ Magnemite on Route 222 and Fuego Ironworks (Requires Surf). You can simply evolve a Magneton inside Mount Coronet by feeding one rare candy
or you can swap Magnezone with Drapion, a great Poison/ Dark type Pokemon that you can catch as a Skorupi in the Great Marsh. Its movepool is good, and its Dark Typing is a great help in beating Lucian, the Psychic-type specialist member of Elite Four.
Suggested Ability for Gastrodon: Storm Drain
Suggested Moveset for Gastrodon:
Surf or Muddy Water, Earthquake, Ice Beam, Hail
• Surf for STAB, and to surf around. Muddy Water is also a decent option, but Surf is much much better.
• Earthquake for powerful STAB. you can solo the Sunyshore Gym with only your Gastrodon's Earthquake. Earthquake TM can be found on the same cave where you can find Gible.
• Ice Beam for coverage against its only weakness, Grass types. You can get Ice Beam on Route 216, though this requires Rock Climb or get it via the Arcade Corner in Veilstone City.
• Rain Dance
Suggested Nature for Froslass: Modest
(Froslass has much more special attack moves in her movepool)
Suggested Moves for Froslass:
Ice Beam, Shadow Ball, Psychic, and Thunderbolt
• Ice Beam for STAB
• Shadow Ball or Ominous Wind [Shadow Ball is much better, but if the Shadow Ball TM is already used then you can opt for Ominous Wind. Froslass learns it via level up].
• Psychic for coverage
• Thunderbolt for coverage [Can be get from the Veilstone Arcade Corner]
Suggested Moves for Magnezone:
Discharge, Flash Cannon, Thunder Wave, Mirror Coat
• Discharge [Can be learned via level up]
• Flash Cannon [Can be received from Byron]
• Thunder Wave [Learned via level up]
• Mirror Coat [Via Move Rememberer]
Suggested Moves for Drapion:
Bug Bite, Poison Fang, Ice Fang, Crunch
• Bug Bite, learned by Skorupi at level 34
• Poison Fang, learned via level up
• Ice Fang, coverage against its only weakness, Ground types [Can learn the elemental fang moves]
• Crunch, for coverage