It's been established at this point that the Norse knew of the North American continent. While evidence of trading posts exist, no permanently occupied settlement has ever been discovered. What if this was different?
The extent of the trade between the European and North American continents is a little-studied area of history. In this TL, we'll manipulate events so that the North American trade route increases in importance drastically. And along the trade route will travel plagues, technology, populations (not necessarily how you'd assume) and faith.
Our POD is mainly religious in nature. ITTL, Christianity spreads over Eastern Europe much faster. This is because Attila (popularly referred to as the Hun) encounters a missionary in his youth and converts. During Attila's rise to power over the rest of the Hun Confederacy, the ruling class adopts Christianity. Over the next few centuries, more and more of Eastern Europe's population will adopt a mix of tengriism and the hun brand of Christianity (referred to as the Scythian Church). This generally leads to their assimilation into what will be Orthodox Christianity. By the dawn of the 9th Century, Eastern Europe is almost entirely Christian.
Though it strains credibility, this doesn't butterfly away most of Europe's political history. This is basically because I don't want to devote the necessary time to Europe; this timeline is at its heart about North America.
The effect of this is that upon their conversion to Christianity the Norse suddenly find themselves bereft of a supply of thralls. As Slavic slaves had been the backbone of the European slave trade, this was very problematic to their economy. Fortunately, an alternate source of non-Christian slaves had been made available. These "Skraelings" should do nicely...