Just finished a run of the Vikings in DoC v1.16 (development version of three weeks ago; I'm going to update on that).
My Monarch/Normal speed/3000 BC start proved to be a pretty tough run for the "settling of America" goal. Usually, I don't jump before I can run before I can walk, but this time it was the other way around. The infrastructure of my core region was pretty much on the backburner, while my focus was needed on the conquest. Which is pretty accurate, historically, I guess. By the way, Christianity spread almost immediately to me, so I could take full advantage of monasteries and missionaries.
So, I settled the northernmost point of Ireland, focused on culture buildings, had a settler and workers ready once the passage to Iceland was free, then settled Iceland with a missionary, so that passage was possible via the whale tile. And just a bit early, I settled in Vinland in 1050 AD.
For the "control European core", I concentrated on sacking Lutetia, Burdigala and Tarraco asap, but with the intention of NOT holding onto these places. Instead, I used them to stock up on settlers and workers, while my troops went further south and conquered Milano and Rome just as Spain and France emerged. I settled Sicily with a new city, as well. I just needed to hold Italy (great complimentary resources for the Norse, too!), and it seems that Italy is still a conditional spawn, because they don't even emerged in my game by 1500.
For the "pillage 3000 gold" goal I maxed out on my core, because it meant to get additional conquests. Thanks to the great "sacking" option, I had already looted my way through Gallia and Italy - now I went for the illyrian coast, then Athens and Sparta. With Byzance not existing in my game, the big player in the Near East was Arabia, from whom I sacked Sur, including the Great Lighthouse, which put me above the threshold. This goal was finished in 1040 already, so I wrapped up the UHV at the earliest possible date.
Another benefit of holding Italy: My city of Kalmar finished Notre Dame in 1050, too.
Takeaway message: The Settle-America-puzzle needs to be addressed immediately and was a good challenge of timing, especially combined with the conquest goal and the pillaging goal, which all need to be balanced with the domestic development of Scandinavia. That was both challenging and FUN. The sum that the Vikings need to gather could be increased (5000 gold?) but that would require players to be more aggressive even after the spawn of the other christian nations. Also, I was lucky with my unconquered independent cities. Just sacking Rome got me 500 gold (just the additional "sacking" sum that was not included in the Conquest...!).
Also,
@1SDAN, what was your diff level? I somehow doubt that I could have beaten the America deadline with beelining Compass, on Monarch, but then I also didn't try such a thing. I guess it could be possible to run on 100% science, when you run a deficit and balance it with the pillaging gold. I was a bit more conservative in the spending, and had an average of 40-60% science, and still having a deficit of around -30 or -50 per turn.