First and foremost, who do you like? You can make just about anyone work ingame, the only limiting factors being availability and evolution requirements.
Try to plan ahead for HM's while you are thinking of a team. This means budgeting party slots for HM slaves. Typically, you'll be able to sneak two or three HM's on to your main fighters, since moves like Surf and Waterfall are useful, and fly is not too cumbersome. Typically, you'll end up with two HM slave pokemon, and four pokemon that you actually want to use.
Try to design a balanced team around the remaining slots in the party. By balanced I don't mean balanced type wise so much as a good assortment of roles. For example, a devoted physical attacker, a devoted special attacker, a tank, and a speedy guy for the purpose of sabotage.
If this doesn't help you, then just look at popular pokemon that other users like to field. Try to find some that are readily available (even if in lower forms) within the first few towns. Ampharos, for instance, is available in its lowest form just past Azalea town, and Zubat- which evolves into Golbat- can be found just before Azalea town.
Also, if you have your heart set on a pokemon that cannot be obtained until later in the game, don't feel bad about using someone else in the interim. It doesn't hurt to have a few substitutes in mind.
Finally, don't overlook gift pokemon. For example, you get an eevee fairly early on from Bill. You can more or less mold it into whatever eeveelution you desire, though Leafeon and Glaceon will require you trade to a D/P/Pt cartridge. With the exception of flareon, most of the eeveelutions are superior pokemon.
Koffing\Weezing has a good defence but the rest of the stats are so-so. As a poison type with levitate, it only has 1 weakness which is psychic. If you really want to use it you could try and get I learn a dark/ghost move in case it has to go against them.
Tentacool/cruel is also awesome. Good special defence and range of moves but poor defence (barrier can help here). These guys have the weakness from ground, psychic and electric types so not as great defensively as koffing.
Why not both since you can use tentacruel as you water type and koffing/Weezing as poison?