I say wait until you're actually grinding to 20 to move the magikarp in. Unless you like carrying around useless pokemon. Even then, wasn't Gyrados pretty crap until gen 4 since most of his attacks are special while he has a high physical?
I vote for Red Baron in the last slot for now.
Well third gen Gyarados just needs a different move set. (Return, Earthquake, Two other moves) They aren't terrible. Just not that great, and easily overshadowed by Vapreon