Well, we already have conclusive proof that the Vikings did colonise the Americas, 500 years before Columbus made landfall (unless you discount Newfoundland) So far, everyone's been talking about Europe and East Asia, but there may have been other places in the running as well- including a pretty outside-the-box candidate I came across recently, on another thread. For a long time after the fall of the Byzantine Navy, in the 12th century, there wasn't much to choose between between the capabilities of European Galleys and Arab/ N. African Dhows at the time; and in his
Nuzhatul Mushtaq, written in 1150CE, the esteemed early 12th century geographer and cartographer
Muhammad al-Idrisi reports that explorers had sailed out into the Atlantic from the then Almoravid-controlled port city of Lisbon, allegedly reaching the Sargasso Sea, making landfall in either the Azores or Madeira, and making contact with the Guanche in the Canary Islands.
In an ATL where the Almoravid Dynasty endured and maintained its foothold in Iberia, with the Berbers holding onto their Iberian Atlantic ports and preventing the Portuguese Navy from carving out their own kingdom, al-Andalusian adventurers would almost certainly follow up on these early missions. Upon discovering the trade winds needed for the return journey in the northern Sargasso, an ambitious al-Andulusian merchant could well decide to attempt a trans-Atlantic island-hopping trip hoping to reach China, with the increasing activity of the crusading Christian pirates beginning to run rampant across large swathes of the Mediterranean providing ample incentive to do so. ITTL, the Arabs/ N. Africans would arrive in America in the 13th century, 200yrs earlier than IOTL (admittedly not a 'very early' colonisation of the New World, but early enough to make for an intriguing ATL).