If we can posit the rise of a strong West African state (or perhaps there is no need of that, as long as there is an economically strong region on the West African coast)--well, Brazil is not very far across the ocean from there. If they have good ships and good Atlantic navigational skills they might well find some routes to and from South America.
The nature of your question seems to imply that we don't want to butterfly away the rise of the great maritime empires of the Europeans, whereas if there are West Africans crossing the Atlantic and opening up trading posts and founding settlements in Brazil and possibly north and west along the coasts, that might pre-empt the whole thing, if they can fight off the Portuguese. Then the Portuguese might not be able to reach their goal of circumnavigating Africa and there might not be support for Columbus in Spain. (Strong butterfly theory says that if the West Africans were doing such different things some centuries before the end of the 15th, there will be no Columbus or Ferdinand & Isabella, of course, but other people to take their places more or less. And interactions seem likely between the early Portuguese explorers and the West Africans that could plausibly feed back to Iberia and even the Med as a whole, reinforcing mere chaotic butterfly effects I say we can ignore, with direct cause-and-effect knockons we probably can't ignore.) In particular, if we are calling the western New World "America" we have to somehow preserve the contingent chain of events that led to Amerigo Vespucci somehow getting the credit!
Well, anyway if we just assume the land gets named after Vespucci in Europe somehow, a West African power or maritime region is not totally inconsistent with the rise of Portugal and Spain. Perhaps, if the West Africans are not Muslims, they will welcome the help of Portugal, convert at least nominally to Catholicism and become a partner of the Portuguese? Or if the region is fragmented politically the Portuguese will play off rivals against each other, perhaps promoting their best allies to dominate in the region and arriving at the same result that way.
Then if the Africans are already well established in the New World they might remain a major demographic factor in some Portuguese/African alliance, continuing to emigrate along with European adventurers. Perhaps their early association with Portugal might give extra force to European squeamishness against chattel slavery--it was the Catholic, and notably Iberian, colonies that had the stricter rules regulating slavery OTL, so if those norms are more strongly in place during the early conquests, possibly slavery as such might be illegal from the beginning. Which won't stop other modes of exploitation that almost amount to the same thing, but might pre-empt the African slave trade.
I think the above is a plausible path to a strongly Africanized Brazil, but if the slave trade is prevented I don't see why these particular West Africans would want to settle in such numbers as OTL outside of Portuguese/West African allied colonies, whereas Africans from other African realms would have no plausible channel westward, unless the cultural developments that made for West African transAtlantic navigation were widespread, all along the habitable coast in fact, and made for alternate, rival alliances of other European powers and other African ones, or simply opened a niche for the other West African nations to vie for American opportunities on their own hook. Given the ease with which the slave trade arose OTL, I shudder at how unstable that situation would be if our goal is to prevent the slave trade! Perhaps if the Europeans could be relied upon to shame each other into keeping slavery illegal the danger would be averted, even if some African coastal states were offering slaves for sale? If that works then the sale offers would decline and the motives for taking slaves from other peoples would be weakened. But probably not eliminated! So the temptation to purchase slaves rather than manage freer labor would always be there for competitive Europeans to give in to.
So while I think some African-American populations could exist without the slave trade, especially if the Africans themselves were crossing the Atlantic on their own, I rather doubt we'd get quite the widespread presence of OTL without slavery accounting for some of it. Of course, with the pattern of Europeans partnering with West African powers, perhaps the voluntary African emigration would not all be to nearby Brazil, but some of it to more distant joint colonial projects. But I don't know what would attract Africans to British North America, for instance, even if a major stretch of African coast were allied to England. It gets cold in winter in North America!

Perhaps the Africans would not realize that before they sailed, but it is hard for me to figure why they'd voluntarily face such an unfamiliar discomfort when considerably warmer lands to settle instead would be appealing to them.