No, に doesn’t usually work with 散歩する. The first and third sentences sound equally awkward to me, if not incorrect. If some think they are acceptable, it would be because they feel the sense of either (散歩しに)行く or (散歩しながらそこに)いる. If you find the third sentence less bad than the first, that could be because you feel a stronger sense of 行く in it. In this case, it would be more like “go away” than just “go.”
The particle should be either を or で. The latter sounds like you perform the action of strolling within the boundaries of the place marked with it, or in other words, under the circumstance of you being in that place. を, on the other hand, puts greater focus on the traversing movement through the specified place.
海 in 海を散歩する or 海で散歩する is normally understood as referring to the beach or shore. It doesn’t mean you walk through or on the water. However, we are talking about a typhoon here, and this changes the meaning of 海 a little. Your friend was probably referring to the state of the typhoon loitering over the ocean. Then, で seems to work at least as well as を.
Having said that, though, I would think most people would say 海でも. Even some of the people who would choose で over を might not say 海ででも. It sounds clumsy.
[Edit]
If you want to keep で, you could say 海で散歩でもしてほしい.
[Edit2]
The sentence in my first edit would sound odd in the dialog added in the question later. See the comments below.