I'm not quite sure what happened, but when I went to grind this Magikarp, I told it to use Splash, ya know, because it's a boss. It then told me I had fled the battle. Little did I know Magikarp's Splash leaping mountains was an understatement, and landed in N's castle. Being impressed by my Magikarp, Ghetsis offered me a proposition: Give him the Magikarp and he'll make all of his Pokemon faint without doing anything.
So yeah, my level 1 Magikarp just beat Ghetsis. Challenge Complete.