L’Anse aux Meadows in Newfoundland is widely accepted by archaeologists as Norse.
http://en.wikipedia.org/wiki/L%27Anse_aux_Meadows
So there is not really any grounds for doubting that the Norse made it here around the Year of Our Lord 1000.
The Irish question is more complicated. To date no evidence of it has been found by modern researchers. However, the Norse sagas contain several references to the Irish or some other Europeans preceding them.
http://en.wikipedia.org/wiki/Hvitramannaland
Who knows. I wouldn’t take the Voyage of St. Brendan as history per se, but wiser scholars than I have noticed it does betray a familiarity with the seas of the northern Atlantic.
About the supposed similarity between Basque and Shoshoni, I wouldn’t give that theory any credence unless it were backed up by not just a few shared roots but by a systematic grammatical comparison. Shoshoni is an Uto-Aztecan language with widespread roots in North America, including Aztec—its grammar is very well known.
Although questionable in the minds of most anthropologists, some linguistic evidence might point toward the Iberian Peninsula. In the 1960's, the Morris Swadesh in the Handbook of Middle American Indians, claimed he found a connection between the Nadene (Athasbascan) linguistic family of North America and the Basque linguistic isolate. This connection, he argued, dated back thousands of years. Basque is the only European language to have survived the influence of proto-Indo-European, which entered the Basque region more than 5,000 years ago. One can infer then that Basque language is at least 5,000 years old, and some argue it is far older. The Basque themselves contend they have survived in their homeland for tens of thousands of years. Though Swadesh has been criticized as a lumper when it comes to linguistic correlations, the claim is nonetheless intriguing under the circumstances. It should be noted that linguist Merritt Ruhlen recently reported to have located a language related to Nadene in Asia. Ket, the only remaining member of the Yeniseian family of languages, shares common words like "birch bark" with some Nadene languages. Ket is spoken by about 550 people (out of a total population of 1,100) who live along the Yenisei River in central Siberia (Lysek 2000).