It was a wild shiny Pokemon. From Bulbapedia:
"In Pokémon Gold, Silver, Crystal, HeartGold and SoulSilver, the red Gyarados is found in the Lake of Rage. The player has one chance to catch it and the incident triggers the battle against Team Rocket in the Team Rocket HQ in Mahogany Town. When captured or defeated, the red Gyarados drops a Red Scale. "