Magikarp is found as early as Mount Moon, where you can buy it for 500 Pokédollars. Otherwise, after you get the Old Rod in Vermillion City, it is found in literally EVERY body of water save for the Cerulean gym pool. The same applies for Gyarados after getting the Super Rod.
In any generation, getting Magikarp to level 20 is a huge pain in the ass, and that's a gross understatement. Once it gets past the hump and turns into a vicious sea snake, however, Gyarados can actually replace your Water-type starter, as it is overwhelmingly strong, has great bulk, and has the versatility to boot. The only things you need to fear are Electric-types, as it is doubly weak to them, and Rock-types, which Gyarados can outspeed and nail with an Earthquake. If that’s not your style, you can also use a Gyarados as an HM Slave, but let’s face it, why would you waste this dragon’s stats on such bad moves? With Intimidate, its weak physical defense actually will actually be higher than its Mew-level Special Defense. In the late game, Dragon Dance + Earthquake/Return will obliterate anything that doesn’t resist it. Just in case your Gyarados falls in battle, you’ll be able to find a replacement right off the bat - you might not even have to go through 15 levels of pain to get to Gyarados. Basically, common, strong, fast, bulky... what more could you want in a Nuzlocke?
Rival (Cerulean City): If you plan on using it in this battle at all, evolve the Mt. Moon Magikarp ASAP as Gyarados can take all of what he can throw at you regardless of what starter you chose. Watch out for Bulbasaur's status powders, though.
Rival (S.S. Anne): Same as last time. Spam Bite. Winning is not hard.
Gym #3 - Lt. Surge (Vermilion City, Electric-type): LOL NO. That double weakness will bite you if you try this. Don't.
Rival (Pokémon Tower): If you chose Charmander, same as last time. If you chose Bulbasaur/Squirtle, switch out as his own Gyarados comes in and let someone else with higher Defense handle it if you're not at least 3 levels above it, otherwise the fight will be fairly difficult. If you can negate the Intimidate and have the Secret Power TM from Celadon City, your own Gyarados has significantly better chances.
Giovanni (Rocket Hideout, Ground-type): Sit this one out. Kangaskhan and Onix pose a problem with their high physical Defense, and Bite won't cut it with Gyarados' low Special Attack. You can try, if you're brave. However, Gyarados can get Water Pulse via TM. If you have it, you can use it to KO the Rock/Ground types.
Gym #4 - Erika (Celadon City, Grass-type): If you have Secret Power or Return on Gyarados, go for it, but watch out for status powders. Otherwise, let another Flying-type handle her. Secret Power can be bought in Celadon.
Gym #5 - Koga (Fuchsia City, Poison-type): Gyarados can tank a SelfDestruct like a champ thanks to Intimidate, but don’t try to make it face both Koffings in a row. Also, since Muk and Weezing are both extremely bulky, it’s best to let something that’s super-effective against them handle them.
Fighting Dojo (Saffron City, Fighting-type): Plow through them with Return, since the Hitmons both have very low physical Defense, while Primeape and Machoke can’t do much to you thanks to their shallow movepools. You might want to watch out for Hitmonchan’s ThunderPunch, but it really won’t do much off of a 35 base Special Attack on a base 100 Special Defense.
Rival (Silph Co.): Same as last time, but this time watch out for Pidgeot's FeatherDance, which will annoyingly lower the power of Return/Strength by a significant amount. Switch out if it does that, and keep Surf at hand to fight it. The rest is much easier.
Giovanni (Silph Co., Ground-type): Take out Nidorino and Kangaskhan, then let someone else clean up. If you have Surf, though, you can handle the Ground-types easily if you want.
Gym #6 - Sabrina (Saffron City, Psychic-type): If you're at level 44-45, spamming Return should result in a clean sweep. Just pack Hyper Potions if things get tricky. Gyarados has good Special Defense, and can tank Psychic well even coming from Alakazam.
Gym #7 - Blaine (Cinnabar Island, Fire-type): Gyarados laughs at Fire Blast, but it won't enjoy Take Down from Arcanine. Let another Pokémon like Tentacruel or Golem go against Arcanine, since Gyarados’ pitiful Special Attack causes even a STAB super-effective Surf to only be a 2HKO or 3HKO at best.
Gym #8 - Giovanni (Viridian City, Ground-type): If you have Hydro Pump or Surf on you, consider this free EXP. It is recommended to teach Gyarados Earthquake when you get it after beating Giovanni, as other useful ‘mons such as Golem learn it naturally, and it will give it a new physical toy to play with for the Elite Four.
Rival (Route 22, pre-Elite Four): As the other Gyarados now only uses Special moves, you can set up Dragon Dance and sweep.
Elite Four Lorelei (Indigo Plateau, Ice-type): Set up Dragon Dance on Dewgong, and enjoy ripping Lorelei apart.
Elite Four Bruno (Indigo Plateau, Fighting-type): Setting up isn't an option as the first Onix has Roar, so kill it right away with Surf. Stay away from Hitmonchan and Machamp, as they both have Rock Tomb, but smash Hitmonlee and the other Onix with Earthquake.
Elite Four Agatha (Indigo Plateau, Poison-type): Kill Arbok and Golbat, then let your other Pokémon handle the Ghosts. Earthquake won’t affect the ghosts, as they have Levitate.
Elite Four Lance (Indigo Plateau, Dragon-type): Load up on X Defends, set up Dragon Dance on Gyarados, heal when needed, and enjoy the sweep. If that's not an option, just use Golem on everything not named Dragonair. While Gyarados is capable of learning Ice Beam, its poor Special Attack makes it a poor choice for the TM. With an Attack over twice its Special Attack, you'd be better off just going with a physical move neutral to Dragon, such as Return.
Champion Rival (Indigo Plateau): Kill anything not of the Water or Grass-type, then let other Pokémon handle the rest. Note that, if you profit of one of his Pokémon to set up - but not Pidgeot, as it has FeatherDance and Sand-Attack - you can easily sweep everything here, too. Arcanine and Exeggutor are good candidates for this purpose.
Post-Game: Gyarados can handle Mewtwo thanks to its very good special bulk. However, Mewtwo has Recover. Don't push it and bring heals.
Magikarp starts out with... Splash. By level 15, you get Tackle, which, while infinitely more useful than Splash, isn’t going to do any damage at all running off Magikarp’s pathetic Attack. However, as soon as it evolves into Gyarados, it gets Bite. While it runs off Gyarados’ low Special Attack, it’s a good choice to take Misty’s stars out with. At level 25, it gets Dragon Rage, which is useful for the early-game where every trainer has Pokemon with only 40-60 HP. The only thing left worth mentioning is Dragon Dance at level 50, which will boost Gyarados’s Attack and Speed to astronomical levels. Its level-up moveset besides that is barren, so it will have to rely on TMs for good moves.
TM27 Return should be slapped on Gyarados as soon as you get it, as it will take a good chunk out of anything. Even if it runs off its lower Special Attack, TM03 Water Pulse and later on HM03 Surf will be a necessity on it, as every Pokémon needs at least one STAB-boosted move. TM26 Earthquake is a great option on it, as it will hit everything Surf+Return can’t hit. With those three moves, it will hit everything for at least neutral damage. If you’re VERY lucky, TM10 Hidden Power might get a spot on the team if it's Flying-typed, but let’s face it, we’re almost never lucky in Nuzlockes. TM06 Toxic is an option, as it works well with Gyarados’s bulk, but Gyarados isn’t the type of Pokemon that stalls out.
Recommended moveset: Dragon Dance / Toxic, Surf / Water Pulse, Return, Earthquake / Hidden Power (Flying)