So, I know its been awhile but given there's no warning I assume its OK to respond. This is a fun and interesting concept to say the least, though each one requires a lot of thought, especially regarding motives given the harrowing nature or simply cost of early expansion.
The Mali Empire is perhaps the easiest to make work, and in the thirteen hundred they were one of the largest empires in the world, and stupidly wealthy. Their relative lack of a navy does raise questions, but its not impossible to overcome, especially as by accounts they did at least seem to get as far as the Canary Current and cos we know smaller ships can make crazy long voyages if designed and used right, Especially as someone sailed a
ship of Papyrus across the Atlantic to prove it was possible. Most seem to think it was led by
Mansa Muhammad ibn Qu which seems reasonable enough. They would most likely land on what is now Venezuela or Guyana, though its possible they would reach mezzo America specifically.
Assuming the former, they'd likely encounter the
Arawaks,
Caribs, and
Timoto-cuicas, who mostly lived as farmers at the time dealing in
maize in the west and
manioc in the east and also dabbled in
oils and asphalts that seeped up through the ground for medicinal purposes, as an illumination source, and for the caulking of canoes. There's also some good islands for pearling in the area and I think all of these would catch the interest of the Mali to one degree or another, especially as corn can be brought home. The exact population of the local people is unknown but its estimate to maybe be 1 million, though how much political organization is... Sparsely covered.
Still, assuming initial violence is avoided, Qu could likely secure the rights to build a port with enough of a silver tongue and gifts, repair and fortify his ships and see about heading home, likely by passing by Mezzo America which could lead to another round of diplomacy. If they manage to catch the Gulf winds, they could very well make their way home on a rather round about trip, though avoiding discovering by Europe may be harder. It may be best for Qu to stay behind and send only a handful of ships back home to try and keep things at a low profile and avoid losing all his progress. A lot also depends on what consequences may have come from Vinland.
But for the time being, let's just say this could start a process of alliance making and colonization, Mansa Musa may not like it, but given he was so inclined to piss away gold and would still owe Qu some loyalty, compounded by the potential of maize would likely lead him to fund another expedition and it could grow from there. Mansa Musa may also deem it a convenient place to send dissidents or trouble makers that can't be easily sold as slaves, or otherwise to extract slaves from.
Now, only Vinland, this is hard because Vinland wasn't really a colony so much as a working station and the land was apparently getting harder to live on. With this in mind, I think you'd need a strong ideological reason to try and stick it out there, or otherwise move there permanently. However, there is one, namely that Christianization was taking place, so a charismatic worshipper of the Old Gods could potentially rally enough people and support to set sail for the distant island only about 120 people ever stayed on permanently to make a new homeland rather than risk persecution or irrelevance.
They'd likely be assumed lost at sea for a time, especially as their contemporizes on Greenland were already struggling and would not be sending ships after them. Assuming they make it they'd want to move to the Southern strip of the island to avoid the worst of the winters, some of the accounts (Semi mythologized) suggest they brought livestock, so they may well have brought bulls, pigs, or sheep and perhaps horses if they were lucky, but it'd be a tricky thing to make work, especially the last one.
But on the assumption it all goes reasonably well, they manage to maintain or begin nominally peaceful relations with the locals, likely the
Beothuk and the
Thule it'd be a hard bitten thing for the first generation or two given the harsh winters the like, but certainly survivable. I imagine it'd take some time before their influence, outside of disease, really spread much as they'd likely spend the first half century just trying to establish themselves, be it with farms, smiths, ships and the like.
Still, once things stabilize and with many things likely having bled over to their neighbors, there would likely be a small baby boom and they could start expanding on the island and exploring further South and beginning trade which would definitely have ripple effects. I think they'd be far from a dominant power, but that their cascading effects of their influence would grow over the course of the next couple of centuries as they integrate into the lands and among the people.
China now, China is flipping hard, like Mali people tended to come to them, but like, even more-so and even bigger. Still, if we're talking around the 1000's to 1300s then we have an advantage because the Yuan Dynasty did like to fuck around and find out, as shown with their naval expeditions against Japan. I'd probably utilize Kublai Khan myself, as he had very expansive interests from reaching out to Africa, to Siam, so wanting to see if there was anything of note to the East doesn't seem too improbable. Especially if someone managed to sell him on the idea.
If they found wholly unknown lands that'd probably intrigue him enough to want it investigated in further detail for commercial and tributary relationships potential. But like with many places it could also be deemed a useful locale to banish large swathes of trouble making people too under the pretense of expanding the empire. What's more the cold in the Northern Areas may not spook Kublai the way it might other leaders. I think it'd likely be fairly vestigial as an investment regardless of whom they meet given the distance, but that might change if someone ambitious enough to want to carve out their own fiefdom there gets put in charge and things just escalate.
Conclusion:
So yeah I think Mali would put in the biggest initial investment and likely be the first to start engaging with the mezzo American states, though likely not in any sufficient degree to try (& likely fail) at overthrowing them. What's more, despite being officially Muslim, the average citizen was very much usually not and even the ruling class did not observe many facets of Islam, for instance we know from that one tourist that he was scandalized to see how women could walk topless, even royalty and that friendships between men & women were deemed good practice ETC. Chances are, much of the population sent to colonize and trade would not even be Muslim so religious tensions would probably be fairly marginal.
Vinland would be less colonization and more integrations and dispersal, they'd be unlikely to have the numbers to pull off any major conquests and would be served better by collaborating. This would lead to a knock on effect with certain livestock being introduced, more naval exploration and trade via the Eastern Coast and iron working being introduced. Whatever Vinland forms or becomes a part of would likely be a very distinct state unto itself I am thinking.
Finally the Yuan would, unless someone got some very big ideas, likely view this Eastern land as more a curiosity than anything else, the side project of a side project. But again, get someone charismatic and charming enough with suitable ambition and it could go from "Oh that's interesting" to "Wait whose building a city where!?" that could easily go unexpected place.
As for local responses, I imagine the time involved in travel, investment, the lack of gun/cannons initially and a multitude of other factors would mean that even with diseases introduced the political instability would never reach the same degrees it did OTL. What's more the Spanish were stupidly, stupidly lucky in their ventures, such luck is not liable to happen here, especially given the drastically altered circumstances.
As a result, while Mali would likely build a respectably size Empire on the East Coast, they'd likely not take mezzo America or the Andes. Vinland would likely be one state among many rather than a hegemon. While the Yuan is less certain but still only have so much time and people. This means much of the lands that make up the modern USA would likely remain semi untouched at least for a good while and have already bounced back from some of the fallout of foreign diseases and begun adopting stuff like horses.
Those are just my theories.