My very first Pokemon would be my actual first Pokemon, Charmander. Sure, the Rock weakness would hurt like hell after its evolution, but by that point, I'd have a solid Grass-type or Steel-type to take care of it. Treecko and Totodile are also great choices.
Counting Pokemon that aren't traditionally starters, I'd say Sandile because it is just so unbelievably badass. Petitlil, Trapinch and Elektrike are also Pokemon that I'd love to start off my journey with.
At the end of the day, though, I'd most likely end up picking up some random Poochyena near the first route and running off while yelling "I'M GOING TO BE A POKEMASTER!" before getting promptly killed for my stupidity.