First things first -- in order to get China to North America, they need to have ships worthy of crossing the Pacific. The Yellow, South and East China Sea and nearby waters are relatively protected from the wild Pacific and that's what the junks are designed for. You need a tradition of open-ocean seafaring, probably starting from chasing open ocean fish like tuna. The junks are already sort of capable and blue-water junks would eventually be common in the 19th century, but you've gotta push for an earlier development.
Also, the only viable routes for Chinese to get to the Americas are by traveling up the Pacific coast or making a stop at Hawaii. Both ways are fraught with their own dangers. Hawaii is technically a shorter route to the Americas proper, but involves a long sail into the unknown. The Aleutian Islands require less ocean-crossing, but you'd best go there in the summer and aside from furs, the lands going eastward will appear very unappealing. And both are long, long ways; longer than the longest distance from Europe to the Americas.
@Thesaurus Rex, interesting point. Instead of having contact being made via explorers, could it be due to refugees instead. All dynasties end eventually. In my current draft the Song is followed by a government called the Chau Dynasty. I could have them blame the Song for weakening China and allowing northern China to fall to the Jurchens. The Chau could attempt to arrest or kill those associated with high ranking Song officials. The Chau could be attempting to secure declarations of allegiance from nations in Asia, the Middle East and West Africa. Those hunted by Chau could be attempting to flee out of the known world in order to keep themselves and their families beyond the reach of the new government for as long as possible. Nations may be unwilling to permanently take in refugees for fear to angering the Chau. How long would the Song be likely to last before they collapsed?
Almost possible...refugees typically don't go into the great unknown, so it would be preferable if they already knew where they were going. If ships can get blown off to the PNW or Hawaii and safely return with knowledge of their existence, the higher classes may have a somewhat better probability of voyaging to those places.
We could have cultures from North and South America send fleets to find China to open up a trade route. Would this situation result in at least part of the fleet reaching Peru? Perhaps the fleet sets up their homes further north but an exploration fleet (some of the ships they arrived in looking for allies and resources) goes further south? Are the folks fleeing westward (deviating eastward temporarily around the Song/Chau coastine) likely to stop in West Africa or continue on to South America along the ocean currents. Would any of the refugees even go as far as the Americas?
Funny enough, East Africa is a rather likely candidate for a Chinese exile state; it was a known location to China and a trade network was regularly maintained with Chinese products showing up on the Swahili coast (and from there ending up all over Africa).
As for the Americas it would be more likely if the Chinese exclave built up enough to have a shipping tradition of their own that eventually reached South America, and better ship technology spread there. South American balsa rafts could travel fast and reasonably far, but had a time limit before they got waterlogged. Going to China in them is definitely a no go.
If they've already made it to West Africa, why go further? Especially if you don't know what's beyond.
Okay then. How about another possibility?
We don't go with Dynasty collapse of Jin or Song as the cause of the fleets discovering America. The Chinese would not even be exploring. As Thesaurus Rex said before Zheng He's voyages were more like the Great White Fleet. What if the motivation for sending ships beyond known waters wasn't making contact with new countries but an exercise in demonstrating Chinese superiority and stroking their own ego? The goal would never be to explore but simply to circumnavigate the world? The Song think they're the best at everything. They have simply picked a feat that they think is incredibly notable and as far as they know is unprecedented. It would be a demonstration of how superior they are to others and would allow the scientific community in China to verify calculations made prior regarding the size of the globe.
Prior to the attempt there could be more than one smaller voyage gradually mapping out a route around the world and determining possible resupply points. Wouldn't want the shame of losing your circumnavigation fleet into unknown waters. Each of these voyages would result in tech and the resulting maps being spread around the world. The official attempt would circumnavigate the world and from then on most naval activity simply stops and China goes back to its original sphere of influence. The other nations simply develop on their own with what they've learnt and received as the fleets passed through. The South American and Central American civilizations now knowing about civilizations further north begins sending trading ships to the Pacific North West. The civilizations of West Africa, now with comprehensive knowledge of a good chunk of the world, trade with East Africa and the West Coast of North and South America.
You're making minor shifts in culture. This will allow you to do many things in an alternate history TL and is a great start. The Song already were great producers of science and technology, but this goes a bit further. Note that even Zheng He's voyages, while bringing back lots of neat treasures, were seen as a frivolous expenditure. More emphasis and prestige will have to be placed on purely exploring and discovering as part of the quest for knowledge.
The best way to start this would be through challenge, as the sovereignty of the dynasty feels shaky. There could be nearby empires that compete for its influence, or a new dynasty that feels the need to prove itself. Your Chau (Chao?) dynasty might actually be up to this task. It may also need a Eurasia that is more interconnected, allowing world maps from every region to complete a better idea of the Old World. Knowledge, trades and technology flowing around will not only provide the Chau with sufficient seafaring tech but may cause them to question China's place in the world (and their legitimacy as a dynasty with a true Mandate of Heaven). Questions might arise of ways to prove the sovereignty of Chau. A treasure voyage like the one Zheng He took OTL may be proposed, but someone may bring up the fact that not only are there numerous poorly or unexplored regions of the earth, but that the planet itself has not yet been circumnavigated. Whether or not the rest of the world considers this a big deal may be irrelevant; what matters is that your culture-shifted China has begun to place emphasis on being the intellectual as well as metaphysical center of the world. When America is discovered, some scholars might compare it to the legend of Fusang and proudly proclaim a mythical land has been 're'discovered.
Scout fleets with enough trade goods to sustain themselves (as well as hunters, fishermen etc) like you proposed could work to scout out terrain for the initial circumnavigation, which may gain more importance than the planned 'treasure fleet' as more of the Americas are discovered and reported back. By the time they discover Mesoamerica and especially South America, attention might shift away from circumnavigation and towards trading with them for gold and silver, which would create a very lucrative trade network if one existed.
Along the exploration of the Pacific coast it will be noted how none of the cultures have gunpowder, steel or horses (this may be different if it ties into your high-population TL), but rich in some other things. This may pique the interest of some would-be conquerers, and may definitely be used to China's advantage in setting up trade colonies that would be necessary to maintain the networks. American precious metals will greatly benefit China proper and there would be a demand for Chinese silk, gunpowder and other weapons technology, and domestic animals (the last of which may have to wait until the trade colonies are set up).
Though China can theoretically conquer some parts of the Americas in its early stage of exploration, military influence would be minimal as well. As such your refugee idea could also work here once the trade network is set up and people can migrate to the river valleys of the Northwest Coast.