Typhlosion / Starmie / Tangrowth / Dragonite / Gengar / Mamoswine
Did my playtrough of SS with this team. And it works amazingly.
Typhlosion

Ability: Blaze
- Flamethrower
- SmokeScreen/Mud Slap
- Strength
- Dig
Typhlosion has a horrible movepool unfortunately, though this set proves it's worth.
Flamethrower is STAB. Until you can have the tutor teach it Mud Slap, have it learn SmokeScreen. Sort of like a filler, but lowers the opponent's accuracy, which is great ingame. Strength is a HM necessary for completing numerous puzzles throughout the game. Dig allows you to escape from caves and whatnot, and is decent coverage.
Get Cyndaquil as your starter. Evolve it.
Starmie

Ability: Natural Cure
- Surf
- Psychic
- Thunderbolt
- Waterfall/Whirlpool/Ice Beam
A classic that I use whenever I get the chance.
Serves as your Surfer, which is necessary to cross water. Psychic and Surf are STAB, with the latter allowing you to cross water. Thunderbolt is coverage. The last slot is your choice of HMs, or Ice Beam, which provides wonderful coverage. It also possesses one of the best Abilities in the game; Natural Cure.
Find Staryu at Route 47. Use a Water Stone on it. Use another Pokemon to Surf until you find it.
Tangrowth

Ability: Leaf Guard
- Energy Ball
- Synthesis
- Growth
- Sludge Bomb
Another one of my favourites.
Energy Ball is STAB. Synthesis heals you, which can keep you from using too many Potions and such. Growth gives you a nice little boost to your Special Attack, allowing you to hit extremely hard. Cut is a useful HM. Tangrowth itself completes the Grass / Water / Fire synergy, which is very helpful ingame.
Find a Tangela on Routes 21, 28, and 44. Level it up with AntientPower learnt. You may also find it at Mt. Silver, but that is much later in the game.
Dragonite

Ability: Inner Focus
- Dragon Dance
- Dragon Claw/Outrage
- ExtremeSpeed
- Fly
Yes. It's a Dragon...
Dragon Dance is still a wonderful boosting move ingame, and means trouble to anything that doesn't resist your STAB moves. Dragon Claw and Outrage are a choice. Dragon Claw is solid damage, while Outrage does more but it's side effect isn't too appealing ingame, though it is a more viable option since you can switch when you beat a Pokemon ingame. ExtremeSpeed is exclusive to the Dratini received in Dragon's Den, and provides Dragonite with priority. Fly is one of the most helpful HMs in the game; and what's more is that Dragonite gains STAB from it.
Dratini can be found whilst Surfing in Dragon's Den. Evolve it. Though the gift Dratini from the same location gets the valuable ExtremeSpeed if the questionnaire is answered 100% correctly, so make sure you use that one.
Gengar

Ability: Levitate
- Confuse Ray
- Sludge Bomb
- Shadow Ball
- Rock Smash/Pain Split
A Pokemon available early in the game, and screws over Bugsy :D
Confuse Ray is my choice over the usual Hypnosis, due to it's accuracy. Confuses the opponent, very helpful. Sludge Bomb and Shadow Ball are STAB, and are a relatively obvious choice. Rock Smash is another HM, and fills for Gengar's lowly movepool. Pain Split may also be used, but it isn't nearly as effective as it is competitively ingame.
Capture a Gastly at Sprout Tower at Violet City and evolve it.
Mamoswine

Ability: Oblivious
- Ice Shard
- Ice Fang
- Earthquake
- Stone Edge
Amazing Pokemon. And screws Clair and other annoying Dragons.
Ice Shard is priority and one of the few decent Physical Ice moves around. Ice Fang isn't really preferred, but it's improvable power is made up for somewhat by it's chance to freeze. STAB. Earthquake is more STAB. Stone Edge is coverage.
Find a Swinub at Ice Path, just before you fight Clair in Blackthorn City. Evolve it.