This is a tricky workaround, but you'd modify the Civilizations XML, have the UB for the new civ replace the old Palace, and that new UB grants a building in every city for free. This new building has the effects of the trait you would like, like +1 gold for every sea tile or what have you.
No need to go THAT far; there's no need to do anything to the Palace. There are two easy ways to do this:
1> Just take a building that every coastal city would have (say, the Lighthouse) and have THAT building be replaced by a UB. So this civ would, instead of a normal Lighthouse, get a "Super Lighthouse" that adds the gold, food, whatever in addition to the normal Lighthouse effect. No need to add a new building class or screw around with the Palace.
The downside is that you wouldn't get the bonus until after you'd completed a lighthouse in each coastal city, but that's minor. On the plus side, if you conquered an enemy city, their lighthouse (if it survived the capture) would automatically be replaced by your super-lighthouse, and vice versa (if they capture your city they correctly lose that extra bonus).
2> Alternatively, just create your new building class and new building type, and set <FreeStartEra>ERA_ANCIENT</FreeStartEra>. This'll give every city a free copy of this building for any game starting in that era or later... which is every game. (Note that "free copy" just means you get the building with no need to build it. You'd still have to pay any gold maintenance on the building.)
The downside to #2 is that if you capture an enemy city, it won't have this building in it, so you'd have to build it yourself. You'd also need to set <NeverCapture> on it so that someone conquering your city wouldn't get it, but this means that if you recapture the city it'll be gone. So you can't set its cost to a negative value, or else you'd never be able to make a new one.
You can mix the two approaches: make a Super-Lighthouse, and set its FreeStartEra to ERA_ANCIENT. All of your coastal cities would begin the game with one, where you wouldn't even need to wait to research the right tech (which might be a bit unbalanced in the early game), but any city you founded would get it without having to build a lighthouse. (Downside: the gold maintenance on the Lighthouse. And you'd still have to build one in captured cities if there wasn't one already.)
for every sea 
and +1 
for every coast city
