Rosslyn Chapel in Scotland, built by the Sinclairs in the first half of the 15th century, has detailed carvings of a number of plants that are native to North America. (Maize being the only example I recall.)
A quick look on the web turns up this page which may be of interest:
There are indeed many stories about people from various places who would have made it to Americas before Colombus. Personnaly, I do not doubt that occasionnally some explorers, fishers, possibly traders or lost sailors could have landed there. The point is that it had no influence on the course of history until Colombus managed to involve the kings of Spain in his exploration.
Funny and pleasant stuff, though…