Magikarp isn't a good idea as it requires some switch-grinding. You don't need a water-type anyway since chances are you'll master ball Palkia and have him defeat everything, and HM duties can be covered by a Bibarel beforehand (those guys are horrifically common mid-game).
Chimchar is an excellent choice, Starly is probably a must imo. Turtwig is good too if you want an easier time against Roark and Wake, though it sucks against Plasma grunts until Torterra. An ice-type is useful to keep around, if only for Garchomp.