Take a look at the following two papers which will give you a feel for how these sorts of enumerations are tackled (typically by methods of generating functions), and will also serve as a bit of a guide to the early literature:

[Here's a fairly accessible and readable article by Tutte](http://www.ams.org/journals/bull/1968-74-01/S0002-9904-1968-11877-4/) which doesn't cover your case but serves as an introduction to how map enumeration problems have been treated mathematically.

[Here's a review by Bender and Richmond](http://linkinghub.elsevier.com/retrieve/pii/0095895686900869) which also describes how to solve some more general versions of map enumeration problems.  I'm not sure if it covers your case or not, since I haven't quite managed to formalize what you're looking for, but if you read these papers you should have a good shot at figuring out for yourself where you need to look next.  

The duals of the maps you are studying are definitely planar triangulations, and I think that since you don't allow loops in your maps that the duals must be 2-(vertex-)connected triangulations.  Since you are considering the "ocean" to be distinct from any of the regions in the islands, I believe this gives your triangulations a root vertex. So my gut feeling is that you want to look at 2-connected rooted triangulations (which if I'm not mistaken were treated by Tutte), but I'll leave it to you to check this guess.  I'm still confused about the rooting, but I think looking at triangulations is better than in terms of cubic maps - if you think of your maps without taking duals, then some pairs of vertices have multiple edges (the results derived in the paper mentioned by Igor Rivin are precisely where maps with such multiple edges are excluded).  

Lastly, (just for fun, perhaps) there is also a large literature in the high-energy physics / field theory community on planar map / planar graph enumeration due to a connection with diagrammatic expansions in integrals over matrix ensembles.  For this angle, you might start with this survey by [Di Francesco](http://www.springerlink.com/content/q4j4v5w1765h2633/).