Well according to this guide book I have, you can get one on the Abandoned Ship and Route 124. But I'm too lazy and tired now to see if 124 is before Mossdeep, sorry
all water stones require dive, whether it be to steal shards from underwater clamperl, to pick them up off the ocean floor, or to get to the one on the abandoned ship. sorry.