Pokemon Platinum Team-
This is the team I would recommend if you chose Turtwig as your starter. As for how this will work, I will list the Pokemon with their recommended held item and give you three strongly recommended moves on it, followed by the fourth slot being filled with many different move options that you can choose between, as well as explanations and descriptions for why the moves were chosen. Lastly, I will follow up with the ability that I recommend and then finish up with the location that you can receive this Pokemon, and their evolution methods.
Here are the Pokemon that will make up this team-
Torterra, Octillery, Houndoom, Altaria, Electivire, Scizor/Lucario
Torterra- (Shell Bell)
Seed Bomb
Earthquake
Stone Edge
Crunch/Outrage/Wood Hammer/Leaf Storm/Frenzy Plant/Giga Drain/Leech Seed/Curse
Seed Bomb is arguably the best physically attacking Grass type move that Torterra can get, and it has no downsides, so it should be your main Grass type STAB. Earthquake is also STAB and a great move to have. Stone Edge is for coverage, nailing all of Torterra's weaknesses for SE damage. Stone Edge and Earthquake together form the EdgeQuake combo, which has amazing neutral coverage. For the last move, Crunch can be used for additional coverage, and can be useful against Elite Four Lucian. Outrage can be another option, and can hit Cynthia's Garchomp hard. Wood Hammer can be another, and will hit even harder than Earthquake at the cost of recoil. Leaf Storm or Frenzy Plant can be used if you want a really powerful move and want to make use of Torterra's Sp. Attack stat. Giga Drain or Leech Seed can be used for recovery. Curse can be used for setting up, and is a great move for Torterra, as Torterra has very good Physical Attack and Defense, but not so great speed. The only ability that Torterra can have in this game is Overgrow.
Location: Starter, pick Turtwig, given by Professor Rowan on Route 201. Evolves into Grotle at level 18, then Torterra at level 32.
Octillery- (Splash Plate)
Surf
Waterfall
Ice Beam
Energy Ball/Charge Beam/Psychic/Signal Beam/Flamethrower/Gunk Shot/Flash Cannon
Octillery is a very underrated Pokemon with excellent base 105 Attack and Sp. Attack stats and an incredible movepool. For its Water type moves, I would recommend Surf and Waterfall, because they are helpful HM's for getting around, as well as the fact that they are both powerful STAB moves and this way you can make use of both Octillery's physical and special attacking stats. The next move I would recommend is Ice Beam, since this is a fantastic move that will help cover its weakness to Grass and hit Dragon types that resist Water hard. This move also works well against Cynthia's Garchomp. For the last move, Octillery's movepool is so wide that you can really pick whatever you want. Energy Ball can be used to counter Water types that would otherwise resist its moveset, and also make it a Ground type destroyer. Charge Beam can also be used if you wish to buff it's Sp. Attack and have a psuedo BoltBeam combination. Psychic and Signal Beam can be used for their added effects of lowering the foe's Sp. Attack and confusing the opponent, respectively. Flamethrower is an interesting and unexpected move on Octillery and is quite fun. Gunk Shot and Flash Cannon can be filler moves if you don't wish to use them on anything else, or don't like the other moves in Octillery's fourth moveslot. For the ability, I would recommend Sniper, as critical hits will deal triple damage instead of just double damage.
Location: Catch Remoraid with a Good Rod on Route 213. At level 25, it will evolve into Octillery.
Houndoom- (Wise Glasses)
Flamethrower
Dark Pulse
Thunder Fang
Fire Blast/Nasty Plot/Crunch/Sucker Punch/Taunt/Sludge Bomb/Hidden Power
Another underrated Pokemon joins our team! Houndoom is an excellent Pokemon and arguably the best Fire type in the game if you don't pick Chimchar. For the moves, Flamethrower and Dark Pulse are both a must, as they are powerful STAB attacks with no downsides and come off of Houndoom's wonderful base 110 Sp. Attack stat. The next move I would recommend is Thunder Fang, as Houndoom also has a solid base 90 Attack stat, and this move can come in handy more often than you would expect. For the last move, you can choose what you like to round out Houndoom's set. Fire Blast can be chosen if you want extra power over Flamethrower, Nasty Plot can be used to boost its stellar Sp. Attack stat to staggering levels, Crunch can be used if you want a physical Dark type move, Sucker Punch can be used if you want a priority move on Houndoom. Taunt can be used as a utility move and Sludge Bomb is a filler move if you want. If you get a good Hidden Power (like Grass or Fighting) on Houndoom, you can also use that. For the ability I would recommend Flash Fire as it will grant Houndoom a makeshift immunity to Fire and that can help it switch in more often.
Location: Route 214, catch as a Houndour. Houndour will evolve at level 24 into Houndoom, which is only a level or two from when it is caught!
Altaria- (Leftovers)
Fly
Dragon Claw
Earthquake
Dragon Dance/Toxic/Fire Blast/Dragon Pulse/Draco Meteor/Sky Attack/Roost
Next up on the roster, we have the beautiful cloud dragon, Altaria! Fly should be it's main flying type STAB, as it is arguably the best Flying type move that Altaria can learn and is a useful HM for getting around Sinnoh quickly. Dragon Claw should be it's next move as it is a good STAB move with no downfall. Earthquake is the third move and is a great coverage move to hit Steel type Pokemon with. For the last slot, Dragon Dance is a good idea if you want to make Altaria into a sweeper. The set is physically based, so that could work pretty well. If you don't want to do that, Toxic can be used to whittle down foes. Fire Blast works as another coverage option, nailing Ice type Pokemon for SE damage. Dragon Pulse can be used if you want another STAB and if you want to make use of Altaria's Sp. Attack stat, same for Draco Meteor, but with more power. Sky Attack can also be used if you want a lot of power, but keep in mind it has to charge up. Roost is good option if you want recovery, as Altaria is very bulky and can take hits well. Natural Cure is the only ability it has in this game.
Location: Route 210, northern (foggy) section. Catch as a Swablu, and it will evolve into Altaria at level 35.
Electivire- (Expert Belt)
Thunderbolt
Ice Punch
Brick Break
Fire Punch/Flamethrower/Psychic/Rock Slide/Signal Beam/Thunder/Thunder Wave
For Electivire, I choose to have Thunderbolt over ThunderPunch because I want to make use of it's good 95 base Sp. Attack, and have a mixed attacking Electivire. Plus ThunderPunch isn't as powerful and can be nerfed by Intimidate (which Gyarados have, and can be a real pain to deal with). Ice Punch is there as it takes care of Electivire's only weakness, Ground, and grants very good neutral coverage alongside Thunderbolt. Brick Break is there for more coverage, and because the team does not have any fighting type moves on it. For the last slot, you can use Fire Punch or Flamethrower if you want a Fire type attack. Psychic is another good special attack you can have on it to take care of Fighting or Poison type Pokemon. Rock Slide is there as its a neat filler move and can make the foe flinch, as well as make Electivire the perfect counter to Flying types. Signal Beam is there for the confusion chance. Thunder can be used for pure power, or Thunder Wave can be used instead for utility. Motor Drive is the only ability Electivire can have.
Location: Route 222, catch as an Electabuzz. Trade with Electrizer to get Electivire. If you can't trade, Electabuzz can still work pretty well.
Scizor- (Life Orb)
Bullet Punch
X-Scissor
Night Slash
Superpower/Swords Dance/Agility/Silver Wind/U-turn/Iron Head/Protect/Substitute/Roost
Ah, Mr. Scizor, my mascot and favorite Pokemon! Scizor is one of the best Pokemon out there and an ideal choice to round out our team. Bullet Punch should be its first move as it is a nice STAB priority and can be very useful. Don't worry about the low power, as Scizor has an incredible base 130 Attack stat, and with Technician its power is buffed by a 1.5x multiplier. X-Scissor should be used for the second move, a powerful Bug type STAB. Night Slash should be in the third slot, as it is a great coverage move to hit Psychic and Ghost type Pokemon and makes Scizor the ultimate counter to Elite Four Lucian. For the last slot, you can slap on Superpower to grant Scizor great coverage and the ability to hit Steel type Pokemon super-effectively. Swords Dance or Agility can be used if you want to buff up Scizor's stats instead, and that is also the purpose of Silver Wind, which can potentially buff up all of Scizor's stats while doing a little chip damage. U-turn can be used for scouting, or Iron Head if you want more power than what Bullet Punch can provide. Protect or Substitute can be used for more scouting as well. Roost can be used to heal off the Life Orb damage, plus Scizor has good defenses and can take hits, so a recovery move is not a bad idea. For the ability, I would definitely recommend Technician, which makes a STAB Bullet Punch all the more deadly.
Location: Route 210, southern (not foggy) section. Catch as a Scyther, and trade with a Metal Coat to get a Scizor.
However, don't fret if you are unable to trade, I've included an alternative option to Scizor...
Lucario- (Life Orb)
Aura Sphere
Close Combat
Shadow Ball
Extremespeed/Dragon Pulse/Ice Punch/Psychic/Flash Cannon
Yup, the mascot of Generation IV himself, Lucario! Lucario boasts amazing offense stats with 110 base Attack and 115 base Special Attack, along with a solid base 90 Speed. Lucario is a real powerhouse and can hit many Pokemon very hard with its combination of powerful attacking stats and a good movepool. I would recommend both Aura Sphere and Close Combat for its STABs so you can have both special and physical fighting STAB on Lucario. Shadow Ball is the third move I would recommend, because of it granting perfect neutral coverage alongside Aura Sphere and Close Combat. For the last slot, you can use Extremespeed as a powerful priority to pick off weakened foes. Dragon Pulse can be used as a niche move to counter Dragon type Pokemon. Ice Punch can be used for that same purpose, plus it can hit Ground type Pokemon (which Lucario is weak to) for super-effective damage. Psychic can be used if you want to hit Fighting types with super-effective damage. Flash Cannon can be used as a STAB filler move, although it provided redundant coverage with Lucario's fighting type moves. Either Steadfast or Inner Focus works for the ability, which ability you choose is up to your own personal preference.
Location: Iron Island, receive a Riolu egg from Riley. Once Riolu hatches, level it up in the daytime with high happiness and it will evolve into Lucario. Keep in mind that Riolu starts off at level 1 which may make it a pain to train up. You can use the Pokemon Daycare in Solaceon town to make things easier on yourself, however.
And there you have it folks. One of the best teams that Pokemon Platinum has to offer you!