It can absolutely be caught. It tends to be on a lot of people's teams due to it being one of very few guaranteed shiny Pokemon, and you can probably find images very easily of people using it.
If you're struggling to catch it, it's probably just bad luck, though I suggesting powering up your team more and obtaining Pokemon that resist Gyarados' stronger attacks. Parasect is great in this role and can put Gyara to sleep with Spore.
Source: I caught it