Even if we ignore the millions of native Americans who lived in the continent before Columbus "discovered" it, even if we ignore other civilizations (eg: Polynesians, Phoenicians, Chinese, Arabs, etc.) who might have been to the American continent...
We still have the Vikings, who have actually established settlements in the Americas centuries before Columbus set sail. And this position is widely accepted, so why is Columbus still considered the one who "discovered" America?
Columbus is traditionally (and indeed still) credited with the discovery of the Americas for a number of reasons, some dubious but others quite legitimate. First of all, we must qualify this discovery as discovery by Old World people. Clearly, the original "discovery" by the human species was some 40,000 years ago by the ancestors of the indigenous populations of North and South America, but given that this original settlement was well within the pre-historical period, and that there has probably been no contact between the peoples of the Americas and the Old World (specifically Asia) in the last 10,000 years, it might be said that we implicitly mean a "re-discovery" (within the historical era) of the Americas.
Wikipedia actually has a fairly well-written paragraph on the subject:
Though Columbus was not the first European explorer to reach the Americas (having been preceded by the Norse expedition led by Leif Ericson[6]), Columbus' voyages led to the first lasting European contact with America, inaugurating a period of European exploration and colonization of foreign lands that lasted for several centuries. They had, therefore, an enormous impact in the historical development of the modern Western world. Columbus himself saw his accomplishments primarily in the light of the spreading of the Christian religion.[2]
Also worth noting is that Columbus led four expeditions to the New World: the first landed on the island of Hispaniola, and others ventured to Cuba, mainland Central America (Mexico area), and the northern coast of South America. Indeed, there is no doubt/controversy that Columbus was the first historical person of the Old World to discover South America.
Over the past few decades there has been some talk and a beginning of tre acceptance of the theory that the Solutrean peoples of southern France/northern Spain made it across to North America on small boats some 20,000 years ago, by navigating the iceburg-ridden North Atlantic ocean. While lying chronologically after most of the waves of migration from East Asia into North America, it is still within the pre-historical period and hence is not usually considered in this discussion -- not least, due to its non-universal acceptance at present.
Now, the first matter is that there exists clear historical evidence (both archaeological and written) that the medieval land the Vikings called Vinland does indeed correspond to Newfoundland, eastern Quebec, and the northern parts of New England. This occurred some time in the late 10th century A.D. (reputably by Leif Ericsson and his crew) when they were forced off course en route to Greenland and landed in Newfoundland. A number of reasons can be given for the diminished importance of this re-discovery, as follows.
The discovery was virtually lost into Viking legend during the following centuries, when the successor states of the Viking homeland (Denmark and Norway) were forged and the Age of Migrations came to a close. As far as I know, conclusive evidence for the Norse discovery only came to light during the 20th century.
The Vikings never made a permanent settlement in North America. At best, they explored around a bit, sailing up some of the major rivers (perhaps even the Hudson), and doing some minor trading with the Native Americans. However, there is no reliable evidence for routine trading with the North Americans, and indeed there are sources suggesting the Vikings considered them to be an inferior people, suggesting most contact with them was probably in the form of skirmishes.
Despite the small inroads made by the Norseman, the discontinuation of any exploration or settlement efforts meant that the long-term relevance of their excursion into North America was of rather little significance. The Spanish discovery and the colonisation, on the other hand, had enormous import on the world has a whole.
The Vikings as a people did not represent a particularly advanced civilisation for the time, except perhaps in warfare. They were not well-educated, and most of the literature surviving from the Viking era is in the form of sagas and the history of kings and rulers. Indeed, it was the case for many years that historians found it quite difficult to separate fact from fiction due to the nature of historical Norse texts.
Now, while Columbus' discovery of the Americas (specifically of the island of Hispaniola) was no more intentional than the Vikings', it did however lead to permanent colonisation, settlement, political and economic expansion of the lands of the Americas by Spain, then Portugal, and finally other European nations. It really comes down to the import of the discovery on socio-political world affairs, which was huge in Columbus's case.
Of course, there have been other rumoured (re-)discoveries of the American continents in historical times, but none with conclusive historical proof, or even a substantial level of acceptance by modern historians. These include rumoured and highly controversial discoveries by the Phoenicians, the Roman Empire, the Israelites, and the Yuan Dynasty of China, as you suggest.
So in conclusion, given the importance of the two verifiable and widely acceptable discoveries of the Americas in modern time, it is not too inaccurate to say that Columbus discovered America. I personally would be quite happy if people said "Columbus discovered central America". To qualify this statement properly, one should really say "Christopher Columbus and his crew were the first people of the Old World during the historical to make a discovery of the Americas that had macro-historical importance." Well, you get the assumptions. Most people unfortunately probably do not realise these assumptions, though I do not think that totally invalidates the statement. Given the proper implicit qualifications, I do believe it is only fair to give Columbus credit for his great skills and daring as a navigator and explorer during this notable period of history.
This is highly speculative and subjective. After all, you put forth very valid contenders to hold the title, particularly the natives and the Vikings.
But what I find most likely is that Columbus was the first to do it for profit. He (and those who paid him) were the first to capitalize on it. The Viking settlement didn't last all that long, and didn't bring back any particular yield to the Viking civilization. Similarly, most native cultures had no notion of profit, but rather community.
He was also the first to discover America in a time of enlightenment and media. (Sure, the media they had then is nothing compared to the instant speed media we have now, but certainly international communication was more efficient in the 15th century than it was in the 11th!) This significantly bolsters the claim that he discovered it, because he was the first to show it to the most people. (And by most people, I mean most people who wrote our history books.)
It is an unfortunate aspect of historical documentation that it always favors those who write it, and typically those who write it are the ones with the money to do so.
Columbus is credited with discovering "America" (the "Indies," actually), because he SET OUT to do so.
He had been trying to find a trade route west, to India, and thought that he had done so; i.e., that what later became the "Americas" was "India" to him, which is why he called the locals "Indians."
Other peoples, the Vikings, the Chinese, and others probably encountered "America," but only by "accident." They did not write home to their sovereigns to tell them that they had discovered a "new world" for their country to settle. Hence, there were no permanent settlements by the Vikings, Chinese, or others.
The one exception was the "Indians" or what we now call "native Americans." But they elected to STAY, rather than "write home" for "reinforcements.
So Columbus not only discovered "America" (from the outside, Europe), but did so in a "official" capacity, on behalf of Her Majesty Queen Isabella of Spain, pursuant to a plan of his own devising.
This is because scientific discovery is not just observing and finding something. Scientific discovery also includes
published results
precise description of your hypothesis
independent testing
Columbus' hypothesis was that he reached India but his published results were reinterpreted as the discovery of the Americas because the scholars determined that India could not be there.
If you just observed a new effect or event, does not mean you made a discovery unless you publish your results.
That said the Vikings while observed the Americas, never published their results. And even if they did, they never thought that the lands were a new continent rather just a set of islands thus they interpreted their results in a way which would not allow to make a discovery.
