If you have Good Rod you can fish a Gyarados from Lake of Rage and teach that Surf. Old Rod will only catch Magikarps from there so you would have to grind it in grass for a while before you can give it Surf. Also with Old Rod you could go to, for example, Ecruteak City and fish in the pond found in the north portion of the town and get a Poliwag.