Well, essentially, you would achieve this by making a melee unit effective at embarking. This way the issue with how to handle promotions and upgrades is put to the side.
What would be good is the ability to get a melee land and naval unit together, kind of like Scythia's horsey double-dip. This would genuinely encourage a civilization to find coastlines and start hammering out ships. Maybe make the ability to heal naval units outside of territory contingent upon having a linked melee land unit.
I started a game as the Norse at what has become my usual settings these days: huge random map on Emperor, -2 AI civ's and -6 city-states. I have to say, the state church is a real throwaway. I mean, it really doesn't do anything besides give extra adjacency bonuses for woods? That is pretty chinsy. At least make it cheaper to build or maintain or something that basically makes it easier for a civ that's building a war machine to take advantage of.
The berserkers don't work, at least not the extra movement. Maybe it's the fact that I upgraded them from spearmen, but they just don't get any extra movement.
I did enjoy getting to sail across the ocean early and explore (given that it was a random map). What I found was that it was one of those two-continent maps, and Sumeria and Aztecs were over there. Unfortunately, the game doesn't currently reduce warmonger penalties over trifling matters like being oblivious to the existence of a civ half-a-world away whose cities are being conquered, so neither are too happy to see me showing up on their shores. But they're buying my spare luxes anyway, and I guess that makes it all worthwhile.