Not a bad idea but I think this would be easier: they should do this like in Total War games (if you played Total War series - Rome Total War, Medieval Total War, Empire TW, etc, you know what I mean). In Total War, most of the times, the harbour is not really near the City... but you can still build ships. And that's because, the region is more important than the city so if the region is near water, you get a harbour and you can build ships (even if the city is far from water).
They can do that in Civ too: the region should be the city + the area around the city (that can be worked by it). A city can expand up to 3 hexes away... so, even if the city is 2 hexes away from the ocean, if it can work a coast hex, then it should be able to build a harbour too (which will appear near coast, not near city, ofcourse). When you build ships, they should spawn at harbour instead of the city.
+ ships should be able to go through forts (without being able to stop on top of them) like in Civ 4, so you can move your fleet to seas inside continents.