Let's compare the Pros and Cons of Fearow and Gyarados:
Fearow - Pros: Spearow can be found very early on, as early as Route 3. Spearow also evolves at a relatively low level 20. Fearow gets access to Fly, so if you don't have a Flier it can be convienient. Its Normal STAB allows it to fire off strong Hyper Beams, which, because of the game mechanics, are quite broken in Gen 1.
Fearow - Cons: Fearow tends to get outclassed in the stat department later on in the game (90 Attack is just pathetic), as well as matching up quite poorly against the gyms. It has a good matchup against Erika, Bruno, and the rival's starter if you chose Blastoise, but struggles against Surge and Lorelei. Plus, its low Special of 61 means that it can be taken out quite easiler by the various Special gyms, such as Sabrina and Blaine. Fearow lacks coverage, only knowing Normal and Flying type attacks, and even then, the more powerful Normal moves such as Double-Edge and Hyper Beam are locked behind TMs, leaving it with Drill Peck.
Gyarados - Pros: Magikarp can either be bought for the absurd price of 500 Pokedollars or fished up with the Old Rod at various locations, making it actually quite accesible. Gyarados also gets the very spammable Dragon Rage, which could help you get out of certain sticky situations. Its high powered STAB Hydro Pump can also help against the rival's starter if you chose Venusaur and Giovanni. Not to mention that Gyarados gets Surf and Strength, two essential HMs for the game. Gyarados also, funnily enough, gets Thunderbolt, Ice Beam, and Fire Blast, meaning it isn't completely useless against Bird Keeper Lance and opposing Grass types.
Gyarados - Cons: Gen 1's crappy mechanics means that Gyarados cannot use its high 125 base Attack to fire off its STABS. Instead, it is relegated to a less-than-superb 100 Special. Gyarados gets no physical moves that are not Normal type, meaning it will have be using the 100 Special more than it wants to. Gyarados also doesn't get a good attacking move better than Tackle until level 41 (Hydro Pump), so you're stuck with Tackle until you get Strength. On top of all of that, Magikarp is incredibly hard to train up, only being found at level 5 and having to be switch trained. It could be quite grueling to level it all the way up to level 20.
With all that considered, my final opinion is Gyarados. The pros that Fearow offer just do not compare to the pros that Gyarados bring to the table. Gyarados has more damage output (100 Special/125 Attack VS 90 Attack) along with more coverage, while Fearow only has its STABs. Gyarados's higher Special also means it can take on high Special threats, and it matches up better against more gyms than Fearow. Despite Gyarados being a pain to obtain, it can be a real powerhouse in the late game. It resists Lorelei's Pokemons' Water attacks, Bruno's fighting, and has Ice Beam for Lance's Dragons. Although Fearow's STAB grants it more powerful Hyper Beams, it is not enough to make up for the overall benefits Gyarados has. Oh, and it can learn two HMs, while Fearow only gets one. Getting a flier isn't that difficult with all the Pidgeys running around as well. Gyarados is just better.
Or, better yet, like sumwun said, just use Dodrio
