[JSND]

Well, if its good enough so...

Totodile

-Availability: Its a Starter pokemon, so its a toss up beetwen the starters
-Stats: Good enough to attack from both side for most in game challenges, and respectable bulk being the so called Physical Defense version of Gyarados.
-Moves: Staple moves in Surf, and pretty good(or maybe average) learnsets. Its early game learnset is pretty acceptable though. It can learn Cut, Strength, Surf, Waterfall, Whirlpool and Rock Smash, which is tons of HMs, and Ice Punch for Dragon Slaying. Strength and Surf generally comes pretty early and gives it good coverage. Bite might help early on....
-Power: No problem against wild pokemon, and most trainers.
-Type: Mono Water is a good typing, and Electric attacks are pretty rare bar Thunder. Grass attacks are relatively rare too
-Match-ups:
Rival 1 : Scratch spam + Level advantage
Bellsprout Tower : Totodile can acquire a solid OHKO in this early game phase. Otherwise, Pidgey and Spearow can provide decent support
Falkner : Not much of a problem even with STAB Water Gun and Bites
Slowpoke Well : Most of the opponent are based around Cave annoyance, so its not a huge problem
Bugsy : No typing, its stats is good enough to handle Bugsy team.
Rival 2 : Bite + Water Gun for non Water resistor. If you has any problem for Bayleef, teach that Dinosaur how to dance in the Gust.
Whitney : Headbutt spamming. If you are using a female Fera it would be easier. A rather troublesome gym, but is doable with optimal grinding
Rival 3 : Surf spam. Ice Punch for Bayleef is still powerful enough to make it a non issue. Note that by now, you can actualy reach Fera.
Morty : You can teach it Dig. Anyway, awakenings, and spam attacks.
Chuck : Strength + Surf. Poliwrath can be troublesome.
Jasmine : Surfin spam. Magnemite level is too low to be a problem
Pryce : It resists Ice, which means it can handle Pryce's attacks. Spam Normal move of choice. Surf the swine.
Rival 4 : Can still win against both Magnemite and Bayleef, but is nowhere as dominant as before.
Clair : Ice Punch + Strength is a pretty solid choice that can 2HKO or OHKO. Beware of Kingdra though.
Rival 5 : Simmilar to ussual case. Surf, and Ice Punch. You realistically cant solo him though.

E4 :

Will : It can use the combination of Surf and Strength to handle most of Will's team. Eggy can be defeated with Ice Punch and Slowbro usually waste their time while you Strength them away
Koga : Just like Will, it generally has solid offense throughout Koga's team, but Crobat Double Team Tactics + Toxic is really troublesome.
Bruno : Just like Will Fera can handle most of his team, although Machamp and Chan can be a slight problem
Karen : Umbreon is irritating, and Vileplume Petal Dance is pretty dangerous.
Lance : Gyarados is a bit of a problem, but assuming level 47-48, All Dragonite bar the level 50 is OHKO by Ice Punch. Aero outspeeds, but doesnt do much unless you are really weakened, although remember that Aero has Hyper Beam.