This is the team I used in SoulSilver and it worked pretty well for me. I don't think any of these are version exclusives, so it should work for HeartGold as well.
Feraligatr @Muscle Band
Ability: Torrent
Moves:
- Waterfall
- Crunch
- Ice Fang/Ice Punch
- Earthquake
Location: Elm's Lab (starter)
Your starter. Waterfall is a great physical STAB, and the only one Feraligatr can get pre-league. Bite destroys Morty's team, and Crunch is even stronger, plus the defense drop is nice. Earthquake covers electric and is just a great move all around. Ice Fang/Punch is coverage for grass and wrecks Lance's Dragonites, but you can't get Ice Punch until the battle frontier, so Ice Fang is probably the better option for a playthrough. The Muscle Band helps its strong physical attacks.
Ampharos @Magnet
Ability: Static
Moves:
- Thundershock -> Discharge/Thunderbolt
- Signal Beam
- Power Gem
- Thunder Wave
Location: Route 32
A really strong Pokemon that you can get before the 1st gym, plus one of your only options for electric-types in the game. Mareep is really nice to have against Falkner, plus static has saved me more times than I can count. Thunderbolt is for STAB/Discharge if you don't want to use the TM. Signal Beam is good against bulky grass types, especially Will's Exeggutor. Power Gem is just for additional coverage, and Thunder Wave is good for guaranteeing paralysis without relying on Static. The Magnet boosts its already strong electric attacks.
Nidoking @Poison Barb
Ability: Poison Point
- Earth Power
- Sludge Bomb/Poison Jab
- Megahorn
- Surf
Location: Route 35
A great Pokemon that you can get pretty early in the game. Its a mixed attacker with a good speed stat. Earth Power is STAB. Megahorn is coverage against Psychic. Sludge Bomb is STAB, and although Poison Jab is physical and through level up, I don't feel like being stuck with Nidorino until level 43 to get it. Surf is coverage against ground and then it doesn't have to be taking up a move slot on Feraligatr. Have your mom save money at the start of the game, and she'll buy you a moon stone to evolve your Nidorino around the time you get to Olivine City.
Machamp @Black Belt
Ability: Guts
Moves:
- Revenge/Low Kick
- Cross Chop
- Rock Climb
- Rock Slide/Stone Edge
Location: Goldenrod Department Store (trade)
For those who constantly complain about Whitney and her Miltank, this is my solution! A great physical attacker that you can get right before fighting the pink demon herself, Machamp should be one of the top contenders for a spot on any Johto playthrough team. Cross Chop is strong STAB coverage. Revenge and Low Kick can be very useful in some scenarios. Revenge is great against Pokemon that outspeed Machamp (which is most Pokemon) and Low Kick is great for big and bulky Pokemon such as Jasmine's Steelix and Red's Snorlax. Rock Climb is for traversing late-game caves and Rock Slide/Stone Edge is coverage for flying and bug. Even if you can't get someone to trade with to evolve Machoke, it's still a very strong Pokemon. I didn't evolve my Machoke until after beating Red, and it still pulled its weight and more.
Togekiss @King's Rock
Ability: Serene Grace
Moves:
- Fly
- Air Slash
- Aura Sphere
- Extrasensory/Psychic
Location: Egg from Elm's Assistant after beating Falkner
The infamous Serene Grace paraflinch Togekiss in all its glory. You had better pray to Arceus that the gift Togepi doesn't hatch with Hustle. Fly is for traversing Johto, Aura Sphere is coverage for Rock, and Air Slash and Extrasensory are used for flinching the living daylights out of your opponents. The Togepi should hatch with Extrasensory. Unfortunately, you can't get a shiny stone until post-league as a first place prize from the bug-catching contest, and Togetic is a very lackluster Pokemon to be stuck with, so I used a Noctowl with Air Slash/Extrasensory/Hypnosis/Fly until you beat the league. If you put the Togepi in the day-care as soon as you can, it should stay at a good level with the rest of your team until you get the stone to evolve it.
Houndoom @Expert Belt
Ability: Flash Fire
Moves:
- Dark Pulse/Crunch
- Flamethrower
- Sunny Day
- Solar Beam
Location: Safari Zone
A strong and fast glass cannon to support the rest of your team. Dark Pulse and Crunch are STAB, and although Houndoom has a slightly stronger special attack, I prefer to use Crunch for things like Alakazam or Gengar, with low physical defense. Flamethrower is STAB. Sunny Day is great for boosting Flamethrower and getting the 1-turn Solar Beam to cover Rock, Ground, and Water. Sunny Day is also crucial for getting rid of the hail during the fight with Red. You can't get Houndoom until post-league, so I used Furret until then.
Furret @No Item
Ability: Run Away
Moves:
- Cut
- Whirlpool
- Rock Smash
- Strength
Location: Route 1
HM slave. Use until you can get Houndoom.
I won't pretend that this team is perfect, or that there isn't any better options, but it got me through the game with pretty much no trouble at all. I think Bugsy was the hardest battle. As a tip, when you get to the tutor in Ilex Forest who teaches you Headbutt, give it to any Pokemon that still have moves like tackle or pound. It's a pretty strong move for early game, plus it can flinch.