I had the same problem.
Go to the route you first need to Surf on, next to Olivine City.
Next, use the Old Fishing Rod A LOT. It will take time, but eventually you will encounter a Staru in SS, and a Krabby in HG. Both these Poke'mon can learn Surf.
Wierd, huh, a Crab and a Sea Star Surfing?