How do I calculate distance between 2 coordinates by sea? I also want to be able to draw a route between the two coordinates.
Only solution I found so far is to split a map into pixels, identify each pixel as LAND or SEA and then try to find the path using A* algorithm. Then transform pixels to relative coordinates.
There are some software packages I could buy but none have online extensions. A service that calculates distances between sea ports and plots the path on a map is searates.com
Pretty much you'll need to split the sea into pixels and do something like A*. You could optimize it a bit by coalescing contiguous pixels into larger areas, but if you keep everything squares it'll probably make the search easier. The search would no longer be Manhattan-style, but if you had large enough squares, the additional connection decision time would be more than made up for.
Alternatively, you could iteratively "grow" polygons from all of your ports, building up convex polygons (so that any point within the polygon is reachable from any other without going outside, you want to avoid the PacMan shape, for instance), although this is a refinement/complication/optimization of the "squares" approach I first mentioned. The key is that you know once you're in an area that you can get to anywhere else in that area.
I don't know if this helps, sorry. It's been a long day. Good luck, though. It sounds like a fun problem!
Edit: Forgot to mention, you could also preprocess your area into a quadtree. That is, take your entire map and split it in half vertically and horizontally (you don't need to do both splits at the same time, and if you want to spend some time making "better" splits, you can do that later), and do that recursively until each node is entirely land or sea. From this you can trivially make a network of connections (just connect neighboring leaves), and the A* should be easy enough to implement from there. This'll probably be the easiest way to implement my first suggestion anyway. :)
Beware of the fact that maps can distort distances. For example, in a Mercator projections segments far away from the equator represent less actual distance than segments near the equator of equal length. If you just assign uniform cost to your pixels/squares/etc, you will end up with non-optimal routing and erroneous distance calculations.
If you project a grid on your map (pixels being just one particular grid out of many possible ones) and search for the optimal path using A*, all you need to do to get the search algorithm to behave properly is set the edge weight according to the real distance along the surface of the sphere (earth) and not the distance on the map.
Beware that simply saying "sea or not-sea" is not enough to determine navigability. There are also issues of depth, traffic routing (e.g. shipping traffic thought the English Channel is split into lanes) and political considerations (territorial waters etc). You also want to add routes manually for channels that are too small to show up on the map (Panama, Suez) and adjust their cost to cover for any overhead incurred.
I reached a satisfactory solution. It is along the lines of what you suggested and what I had in mind initially but it took me a while to figure out the software and GIS concepts, I am a GIS newbie. If someone bumps into something similar again here's my setup: PostGIS for PostgreSQL, maps from Natural Earth, GIS editing software qGis and OpenJUmp, routing algorithms pgRouting.
The Natural Earth maps needed some processing to be useful, I joined the marine polys and the rivers to be able to get some accurate paths to the most inland points. Then I used the 1 degree graticules to get paths from one continent to another (I need to find a more elegant solution than this because some paths look like chess cubes). All these operations can be done from command line by using PostGIS, I found it easier to use the desktop software (next, next). An alternative to Natural Earth maps might be the OpenStreetMap but the planet.osm dump is aroung 200Gb and that discouraged me.
I think this setup also solves the distance accuracy problem, PostGIS takes into account the Earth's actual form and distances should be pretty accurate.
I still need to do some testing and fine tunings but I can say it can calculate and draw a route from any 2 points on the world's coastlines (no small isolated islands yet) and display the routing points names (channels, seas, rivers, oceans).