Well, i suggest catching first a wooper before the second gym.
Then you'll want to get the Eevee and Togepi you'll recieve and evolve them as soon as possible.
That so far is Cyndaquil, Wooper, Eevee and Togepi, but you gotta go to the Pokethlon dome as early as your return to Ecruteak City, so you can buy a Shiny stone to evolve your Togetic.
After that you'll catch a Heracross on your way to Pryce since there are trees on the route that connect to his city that have Heracross.
Then you'll get the Red gyarados to replace your now worthless Quagsire
After that you will catch a swinub on the Ice Cave and train it to evolve it into a Mamoswine in said cave, so you can fight and defeat Clair even easier.
So that your final team can be:
Typhlosion-FIRE
Gyarados- WATER/FLYING
Jolteon-ELECTRIC or Espeon-Psychic or Umbreon-DARK any one of the three will do good in your team.
Togekiss- FLYING/NORMAL
Heracross- BUG/FIGHTING
Mamoswine- ICE/GROUND
All are good pokemon and they'll give you a nice type coverage and no trouble at all to spread the HMs.