*slowly raising head*
The problem with doing it through Mali or Ghana is a lack of port infrastructure. While the Mali Empire theoretically reached the Atlantic coast, it's not like there was a vast port infrastructure or huge cities in what's now Senegal, nor a huge naval tradition - trade was mainly north-south, with Berbers and Tuaregs trading in salt and the Sahelian peoples trading back gold and slaves. Most of that trade was conducted overland. Moreover, the political centre was more towards the Niger than towards the Atlantic coast. You'd need a POD which would result in Mali getting ships in the water. Taking Mansa Musa at his word is tempting, but probably ill-advised.
Muslim Iberia is also possible but, again, you need history to unfold in such a way that Muslims from al-Andalus have a good reason to get a qarib or ten into the Atlantic. They have little incentive to do that; the salt-gold-and-slaves route connecting Awdaghost and Timbuktu to Sijilmasa and from there to al-Andalus is a land route, and most Andalusian trade takes place in the Mediterranean in the form of peddling cash crops. Al-Andalus has the advantage of having caravels before Christian Europe does, considering that the caravel was developed from the Arabic qarib; if you can engineer a reason for Andalusian sailors to want to explore the Atlantic, they'll eventually encounter the Atlantic gyre and the trade winds, and someone will eventually discover there's land over thataway.
That said, would the Moors really colonize? Depends which al-Andalus we're talking about. Are we talking about a surviving Umayyad Emirate or Caliphate? Are we talking about a rump al-Andalus under the auspices of the fanatical Almohads? It all depends.