This is off of the top of my head...
Trade the Red Gyarados to R/B/Y version and teach Mimic to it (have all of its other moves erased, I believe). Now go encounter a ditto and use mimic to transform into that ditto. Then the ditto will transform, etc. Do it for about 2 or 3 times, I can't really remember. But capture the Ditto afterwards and trade it back to G/S/C. It's supposed to be shiny and you'll have 1/46 chances of having a shiny Pokemon from an egg if you bred with that ditto.
=D