China is incredibly disadvantaged by geography here. The wind patterns in the Northern hemisphere are south-east (the so-called "trade winds) in areas nearer to the equator, and north-west in areas nearer to the poles.
What this means is that there is a nice air current flowing from Iberia/West Africa directly to the Carribean and South America. So convenient was this that even before the discovery of the Americas, it would be used by ships seeking to go down to Africa - Portugese traders and the like would end up coming within a reasonable distance of the Brazilian coast (though still far out of sight) just by trying to go south.
This geographic pattern means that, as long as there is a civilization in Western Europe/Africa with the appropriate sea-faring technology and stability to be able to make long-range journeys on a regular basis, they will inevitably discover the Americas, even if just by accidentally sailing too far on the trade winds.
By contrast, this same wind pattern would mean that China would have to use the North-east winds in the Pacific. Rather than being able to travel in a straight line like the Europeans, this route is far more circular (going up towards the poles before coming back to the south). When you also take into account the large size of the Pacific Ocean, this means that the "journey of discovery" for a Chinese fleet could be up to 3 times longer than a European one. And whereas the Europeans were already using the south-east trade-winds to go south for African trade, all the Chinese have to their north is a barren wasteland filled with hostile nomadic tribes, as well as a sea that is far less welcoming (icebergs and lack of easy replenishment) than the warm seas of the equators. Not to mention that the Japanese islands pretty much stand right in their way.
So, for the Chinese to accomplish this, you need more than just a level playing field. You need a full blown Europe and Africa-screw, that keeps the westernmost nations busy with war or social collapse, until the Chinese find some incentive to make the long haul across the Pacific. And it will be incredibly hard to get that incentive; the natural tendency for Chinese expansion would have been landwards (like the russians), towards Central Asia. And even if that avenue was blocked (say, a split China or an enduring and powerful Mongol/Turkic state in the area), the next place for Chinese traders to go would be south, towards the riches of the Indian Ocean (which mind you, might end up making Australia the Chinese new world, but that's not what we're looking for here).
Therefore, along with the Europe-screw, you need to create some reason for the Chinese to start trading towards the north. That means somehow dealing with the steppe tribes that tended to invade from that direction, creating regular sea-based trade-posts, and dealing with interference from both the bad weather and Japanese/Korean pirates or raiders. The most plausible way to combine all of this seems to be the creation of a Machurian-based Chinese state (perhaps as part of a split china), that has an incentive to become a significant sea-power (either trade or war (or both) with Japan is going to be required here). Theoretically, such a state could pull a reverse Viking and hop along the northeast corner of Asia when it is Ice-free, eventually coming to the welcoming lands of Alaska.
That's the only way I can see this happening really.