Newfoundland may be a harsh, windswept land, but it's certainly more habitable than Iceland.
Oh yeah! The OTL British and French had no actual reason to establish pastoralist communities. Comparing Lincolnshire - a center of english sheep farming with Iceland is literally comparing the Shire with Mordor as envisioned by Tolkien.
And gradually as contact between the Union and north America is being established there are the other populations I mentioned that are prime settler material. To be honest, the norse atlantic islands, remind me of the portuguese atlantic islands. While the latter were or temperate climate, they too had an issue of supporting their populations. These tiny islands alone provided a great percentage of the Portuguese colonists to Brazil. And Portugal was the state that exported the most people during the 16th and 17th centuries.
Greater contact, also means more exploration of the atlantic seaboard of Canada and finding places much better suited for agriculture and grazing. The boreal forests of e.g. PEI would seem a really nice place for Icelanders and Feroese.
The beauty of the POD is that it is early. Very early. Even extremely limited migration of first a few dozen and then a few hundred people per year would lead to a demographic boom. The 1666 population of New France was 3,125 people. At 1670 french migration to Canada basically stopped. Even so, in less than a century, New France had a bit fewer than 70,000 people, just by natural increase despite the crown's mismanagement.
Perhaps the Beothuk take up shepherding from a few intermarried Icelanders, thereby forming a more viable niche for their nomadism via transhumance?
That seems quite plausible to me. In any case they will be devasted by epidemis, but the survivors have a better chance surviving as pastoralists.