I agree with Olaf in terms of timeline, including anything previous would be rather tedious, and hugely difficult considering the map. End in 1930, perhaps?
Look at a map of Africa and you will realize that should someone do this, it would require either: a) the inclusion of the Middle East to the east of the Persian Gulf and south of modern Turkey, b) a weird island Africa OR c) a warped map.
However, if we went with a) (which would also require the southern tip of Iberia, Sicily and Greece) a lot of cool things could come of it.
To start, unplayable but necessary nations would be:
Byzantium (to be conquered)
Spain (for the Almohads/reconquista... or should we leave that out? Iunno. Also, colonization)
Portugal (early colonization)
England (major colonization)
France (major colonization)
and MAYBE Sicily (fighting with Moors)
For playable nations...
Moorish Africa/Iberia:
Al-Andalus
Almohad Dynasty/Tunisia later
Almoravid Dynasty/Morocco later
One more, not sure what...
Sub-Saharan West Africa:
Ghana
Mali
Songhai
Kanem-Bornu
Something along the southern coast, possibly Benin?
Middle East:
Fatimids
Arabs
Ottomans (but where to capital?)
Yemen
East Africa:
Ethiopia
Adal/Somalia
Swahili
Central/South Africa:
Mutapa
Zimbabwe
Kongo
Zulu
Obviously more here, but what?
That leaves 18+ playable nations. Scale would need to be fairly small, considering how spread out this all is. There's also a big ole hole in between Ethiopia, Kanem-Bornu Swahili, Kongo and Mutapa. I'm not sure what to fill it with, my impression being there were mostly just tribes in the area. If we could fill this hole, Africa would actually be pretty well-connected.
As for religion, I think Islam (Northern Africa), Catholicism (Europe) and Orthodoxy (Byzantium, Ethiopia) would be the regular religions. Animism (southern Africa, west Africa and the Horn of Africa) would be a regular religion with no diplo bonuses for other Animist nations. It (and Orthodoxy) would also start to disappear as time wore on, if Catholicism and/or Islam were in the same city. Hinduism would be a late game religion that randomly hits cities in the Horn and causes unrest.
That's all for now, time to sleep. 3 hours of sleep for work tomorrow... I have only RFC and myself to thank for this. And this thread, I suppose. I felt a need to contribute.