Interestingly, a single ship with a few men and women accidentally reaching the new world would be enough to start a colony. Making it normal for fishing boats to be "manned" by women (I don't know how much that was the case) might increase the chances for this to happen.
Let's say it happens in the year 900, with 4 couples.
If those first colonists manage to survive the first few years (maybe they land on an Island with no big permanent Amerindian settlement, somewhere around Newfoundland), they'd quickly be big enough to start an offspring of Viking civilisation.
If they know farming (at least some gardening to begin with), they'd even have an advantage over many northern Amerindians.
Once the colony has reached about 200 people (after about a hundred years) it might be able to build boats big enough for reaching surrounding isles and the American continent. That might allow some trade with the natives, which would also be helpful in getting to know which plants can be eaten and how to prepare the ones that can only be eaten cooked, dried, or the likes.
After another 200 years (1200, 20 000 Scandinavians, growth limited by "new" illnesses like Syphillis), there should be several small villages of 10-2000 people scattered over the whole area, some farming, bigger boats, and so on. Wars with the natives will probably be avoided, but some adventurers might destroy small Amerindian settlements in the area (they are still Vikings).
If the Vikings mix with the Amerindians, a mixed civilisation would result, Amerindians would get slightly more European looks and some European technologies. Might lead to interesting changes in dealing with the natives later, when the British, the French, the Dutch, and the Spanish arrive.
If there is no large mixing, there might be some smaller wars when the Vikings try to get to the continent, but there'd probably be little resistance on some isles and in much of the far north.
Both should allow an expansion of the (core) settlement to 200 000 people by 1300, and ships able to cross the Atlantic. After some time, the colonists will probably have contact with the Norse, which should lead to an influx of traders, fishermen, colonists, missionaries, and so on.
If the Scandamericans have stayed pretty Scandinavian in language, culture, and looks, that would be a rather peaceful process, and there'd be a spread of the Scandinavians throughout north-east America quickly. If big differences have developed in the meantime, a small war might erupt, after which the settlements are probably conquered within a few years.
Either way, the north-east of Northamerica turns into a Scandinavian influenced nation, able to fight off explorers from other European powers there. The Spanish and Portuguese start their explorations earlier and conquer the south, pretty similar to OTL, but slower in some places due to more knowledge about Europeans and European abilities in the area (horses and carts might be introduced already).
The plague will probably affect the area a lot, and it will come in combination with Syphillis. Therefore, a population which could have been 2 million by 1400 is reduced to 500 000.
Novascandia, as I'll call the area from now, will become independent at about 1500 (5 million) to 1600 (50 million), as it will be too big than to be effectively controlled by a Scandinavian power, if it ever was. It will also have extended to most of North and East America.
In the year 1700, Novascandia has split into several nations due to internal wars over land, when the population explosion has met its limits of then known technology. Instead of the potential 250 Million people, the intense fighting reduced the population to 100 million people. They are covering all of North America including Alaska, while the area around Florida, Texas and California is Spanish. In some ways, Novascandia is very advanced, and due to more farming much more populous than what the Europeans found at that time there IOTL. In other ways, it probably misses a few European developments - no very free market, no industrialization, and so on. Therefore, the odds in any war against the Spanish are pretty even at that time, especially considering the fact that Spain was still a world power then, and the different Novascandian nations liked to fight each other, too.
By 1800, the population of Novascandia has increased to 500 million people. America doesn't look like the America we know, more like a copy of Europe, with small towns every few miles all over the country, and with a similar population density to Europe (or China, or India, and so on, for that matter). Florida, Texas, and California have been taken away from the Spanish. Thanks to the high population numbers, contact with Europe, and some economic competition with Europe, Novascandia has become as dominating as Great Britain was IOTL at that time, despite a few deficits in terms of technology and economic policy. Novascandian nations were able to grab a few parts of Australia (kind of like Africa IOTL), and, in later wars with GB, get most of the rest of it.
By 1900, the population has reached 1 billion people (not as much as it sounds, considering the big space and the development in places like Europe and China at that time). The technological lead has gone to Novascandia, Europeans form bigger blocks earlier because of the competition. Maybe some wars have lead to a dominating power in Novascandia, maybe Novascandia stays a patchwork like South and Middle America IOTL.
By today, there are 2 billion people living there. That's Europe plus SE-Asia on a twice as large and pretty fertile territory (OTL Kanada, USA, Australia).
Such an increase in population is probably the main difference if America had been colonized 500 years earlier. Not too rosy a vision for our environmentalists, I suppose...