Glitchtaker

Well, you can find Staryu by fishing with a Super rod in the city/town that is directly beside the Whirlpool islands where you get Lugia. I can't remember the name of the town, but it is surrounded by water on the right side and you have to surf to get to it. Anyway, by fishing in the water to the right of that town with the Super rod, you can find Staryu. It's a bit rare, though, so I don't know how long it will take.
As for getting elemental stones, Bill's grandfather will give you one of each, depending on what Pokemon you show him. He is in the house past the Nugget bridge in Cerulean City in Kanto. Make sure you have a Pichu, a Staryu, an Oddish, a Growlithe, and a Lickitung. He will only give you one of each stone, so use the stones you get wisely.
However, there are also trainers around the region that you can battle and they'll ask you for your phonenumber. Only accept if they say something like, "Sometimes I find cool items, and if I find any, I'll give them to you!" If they say something about getting an item and giving it to you, then accept their number. Eventually, they'll give you an elemental stone. The person depends on the stone you get.
To make people call you, fly to your hometown and speak with your mother. Whenever she asks you if it's Daylight saving time, or if you want to switch back, then say 'yes'. Always say 'yes'. This is a glitch to make people call you. Sometimes it may not work, so don't get discouraged.
Hope this helped. Good luck.