I feel that it is necessary to separately answer this part of the original question, as it actually ties in with the original question in a profound way:
I would also like to include that island nations like Greenland were
populated by natives, without any known landbridge to North America. I
have little knowledge on natives and biology and what they stemmed
from (Homosapiens/Neanderthals?) but I do know that they evolved into
humans.
This sounds to me like stemming from an assumption that the human species has somehow sprung up all over the world as independent populations. According to current understanding, Homo sapiens evolved in Africa, and then migrated into other parts of the world. It seems that all currently living humans descend from migrations that took place less than 100 000 years ago. And while there is clear evidence that these populations interbred with previous groups of humans, not all of whom were Homo sapiens, the genetic impact of this is relatively small (a few percent).
Understanding the origins of Homo sapiens may help in understanding why some parts of the world, such as Iceland, never even had "native" human populations before recorded history. Humans appear to have migrated out of Africa over a very long period of time, and – to clarify – "migrating" here is more akin to "expanding" rather than "moving". The first waves left the continent roughly 100 000 years ago, spreading through Eurasia, and from there to the Americas and the Pacific. The extremes of the latter areas were only reached relatively recently, a few thousand years ago. For example, Greenland, which was mentioned in the question itself, was only populated by "the natives" around 2500 BC. And those were not even the same natives that Europeans eventually encountered:
After the Early Dorset culture disappeared by around 1 AD, Greenland
was apparently uninhabited until Late Dorset people settled on the
Greenlandic side of the Nares strait around 700.5 The late Dorset
culture in the north of Greenland lasted until about 1300.[7]
Meanwhile the Norse arrived and settled in the southern part of the
island in 980.
So one could argue that, without Europeans coming from the east, people from the west would maybe have migrated on from Greenland to Iceland, given a few hundred or thousand years. So to answer the original poster's disbelief at Iceland being uninhabited before the Norse, it may well be that Iceland was just so remote that no previous group of humanity had yet had the time to populate it.
But to me the most important point here is the realization that the concept of "natives" is questionable to begin with. From this point of view, there is little difference between the migration of the two groups of humans into (for example) Greenland; "natives" versus "colonists" is simply a misleading narrative, as it's all a part of the same long history of human migration. Another good example is human migration to Polynesia, which took place less than 3000 years ago. In the hundred-thousand-year time scale that humans have been migrating all over the world, there is a time difference of 3% between the "native" Polynesian colonization and the age of European exploration. Homo sapiens evolved inside a relatively small area, then migrated outward from there, so almost everyone is an immigrant or colonist if you look back in time far enough. And, in many areas, Homo sapiens replaced (though not necessarily through direct interaction) previous populations of archaic human species, the "real natives". Who, in turn, replaced previous populations, and so on.
