And other similar theories such as early African/Asian contact?
Outside the Norse in Newfoundland, there really is no credible evidence of earlier Afro-Eurasian contact with the Americas before 1492. There are certainly lots of hypotheses about earlier contact, but they are without evidence at best and obvious frauds at worst, with the occasional swings into overt and covert racism.
The Solutrean Hypothesis is an interesting case that I've seen pop back up recently. It posits that members of the Solutrean culture in western Europe traveled to and populated the eastern side of North America during the last ice age, taking much the route the later Norse would, except aided by the ability to traverse across ice sheets. The supporting evidence is similarities in Clovis and Solutrean flint points and similar prevalences of a certain haplogroup. This seems like a reasonable idea -- a counter-part to the Bering Landbridge -- and was even put forth by a couple of professional academic archaeologists.
The problem is the points aren't actually that similar, and the Clovis style that supposedly circum-Arctically made its way to the Americas does not show up until several thousand years after the Solutreans would have supposedly made the journey. This part of the hypothesis is largely based on outdated notions of the peopling of the Americas to begin with. Older theories reasoned that Clovis point hunters were the first people in the Americas. Yet, most Clovis artifacts are found in the Eastern side of North America, far from the Bering Strait. So it would make sense in this model to argue for a migration from the East. Yet, we know now that migration was actually pre-Clovis, and that this style developed later after groups had already crossed from Siberia into Americas. Closer examination of the genetic evidence further supports this, showing the prevalence of the supposedly European haplogroup much more closely resembles those in Siberia than in Europe. The interesting high prevelances of that particular bit of genetic code in Western Eurasia and Eastern America is simply convergent evolution via a founder effect in the later population.
/u/reedstilt and I have both taken turns at batting the Solutrean Hypothesis around if you want to read further and also check the sources. You can do so here and here. The other thing mentionable about the Solutrean Hypothesis is that White supremacists love it. It allows them the opportunity to create all sorts of fantasy scenarios where Brave White Men who did Brave White Things were the "true" original people of the Americas, not those Evil Brown People. Or something like that, I don't really care to plumb the depths of that particular racist outhouse.
Another hypothesis that seems to have staying power despite the "evidence" having long since been disproven, is the idea that Africans settled in Mesoamerica, and that the giant carved stone Olmec heads actually depict Black Africans. Also, pyramids. There's actually several variations on this them involving various Sub-Saharan and North African groups traversing the Atlantic at various times.
Ivan van Sertima's 1976 book, They Came Before Columbus, is probably the best known formulation of this idea, but it is far from the first. Linguistic Leo Wiener published Mayan and Mexican Origins in 1926, in which he claimed Mayan and Nahuatl showed evidence of having being derived, or heavily borrowed, from Mande languages. There are innumerable other theories as well, especially once you mix in the Pheonicians and Egyptians along with West African groups. Van Sertima himself posited that Olmec civilization -- the "mother culture" of Mesomamerica -- was in fact founded by the Nubian 25th Egyptian Dynasty. This notion persists despite the fact that the Olmecs, and their carved heads, actually predate the 25th Dynasty by several centuries.
I write more on this and a few other Africa connection proposals here. I would strongly recommend the Current Anthropology article, which not only does a thorough debunking of Van Sertima's claims, but also points out that usurping the actual accomplishments of Americans in service to an Afrocentric fantasy is, itself, pretty racist. Just like with the neo-Nazis who draw imaginary connections between themselves and a European group that existed more than 15,000 years ago, Afrocentric views draw a false connection between groups like 25th Dynasty Nubians and the modern descendants of the Atlantic Slave Trade. Both groups do so to the detriment of their own history and to cultures who histories they are trying to usurp. Besides, the mutations for pale white skin, blue eyes, and blonde hair hadn't even occurred when the Solutreans made their supposed journey, stupid White supremacists.
Other groups that show up frequently are the Israelites, the Chinese, the Irish, and, of course, the Romans, with that last group apparently having haphazardly scattered coins and other artifacts across North America to be later found under dubious circumstances by 19th century treasure hunters looking to make a buck. Many of these ideas segue into the long tradition of trying to figure out, "scientifically," the origins of Americans.
An interesting source that I've enjoyed is Davies' Voyages to the New World. Published in 1979, it's one of the few academic omnibus takes on these sort of contact mythologies, analyzing and contextualizing them. It should not be a spoiler to state that Davies (an extremely prominent Mesoamericanist himself) does not give much creedence to any claim, with the exception of the (still relatively newly discovered) L'Anse aux Meadows site. A wonderful non-academic source is Jason Colavito, who has written extensive and incisive debunkings on everything ancient aliens to the Kensington Runestone.
The 11th century Norse settlement at L’Anse aux Meadows, Newfoundland, Canada, has been internationally recognized since 1960. See the Unesco World Heritage Site website for a short summary. There have been many related posts in this sub; search "Viking" or "Norse" + "America" or "Vinland".
FYI, /u/CommodoreCoCo reported bad news for the Polynesia - South America contact proposal that had been kicking around:
Well they aren't really theories. Lief Eriksson had pre-Columbian contact with "the new world" some 500 years prior, although it was not in the mesoamerican (what we consider 'The New World') part of the Americas. It was with the northern part of the Americas. There is more information on this obituary about Helge Ingstad on the matter.
http://www.telegraph.co.uk/news/obituaries/1328355/Helge-Ingstad.html