Two solutions:
One, you can sail galleys and workboats onto Ocean spaces provided your culture boundaries extend over them. In fact, you may not even have to... if your seaside culture boundaries bump up against those of a civ across the waters, it'll put you in diplomatic contact with that leader.
This doesn't help if you're /really/ isolated, but sometimes another land mass is just one or two ocean spaces separated from yours. In my game I bridged a one-space gap naturally without even having to use a culture bomb.
The second solution: Beeline for Optics, which is a lot earlier and cheaper to grab than Astronomy. Caravels can cross ocean squares, although what they can carry is limited (no Settlers yet, for instance). But they can get you in contact with everyone, spread your religion through Missionaries, and if you're focused towards Optics as a priority, dedicate one caravel to circumnavigating the globe first, thus giving your naval units +1 movement for the rest of the game(!). Theoretically you could even use a stack of caravels and explorers to try to take over an enemy city and give yourself a foothold elsewhere--not terribly efficient, but on Noble I got to Optics fast enough I saw cities still defended by archers and spearmen, and a Strength 4 explorer might be able to do some damage there in sufficient numbers. Holding onto the city could be tricky unless you can sue for peace, though.
You can continue shooting for Astronomy as you tech trade with your new contacts (you won't be able to trade resources yet). By the time you reach it you'll hopefully have +1 naval movement and also have found some untouched islands to ship those settlers out to. With the AI in Civ4 as blind and limited as you are, unclaimed islands actually /do/ exist centuries into the A.D. period. Needless to say, giving out your world map early would be a seriously bad idea.
Anyhow, I can't vouch for how well this works on higher difficulty levels, but on noble it worked like a charm. I was horribly isolated on my island, unsure if I was ahead or behind. The 'hands across the ocean' culture trick got me in touch with Victoria, who alas proved to be just as isolated as me, but the caravels worked just as I'd hoped. Be ready to spam missionaries out on them if you founded a religion, though, since a mainland religion will have likely taken hold much more thoroughly. It seems to be a waste of time to convert people who founded religions since they just convert back again soon after, but anyone who didn't found a religion is fair game as soon as you've gotten your religion spread to a majority of their cities. And even nations that decry you as heathen will trade techs to you sometimes when you've just arrived on their shores
