He doesn't appear every week, he takes turns with all the other NPCs like Redd, Katrina, Saharah & Pete (there are others, Pascal, Katie, Joan on a Sunday etc).
If you don't have Pete (he will wander around town at 9 -10am & 5-6pm) and no other visitor, then give your beach a search - including the private beach if you have one (can't get to it without a wetsuit).
Once you have the Police station it gets a bit easier as Booker/Cooper will tell you if there has been rough seas (indicating Gulliver is on the beach).
You can get Pete 3x in a week.