The problem we run into here is that very few sub-saharan languages developed their own writing system prior to the colonial era. Specifically, we have Ancient Merotic (probably), Old Nubian, Nsibidi, Adinkra, and Lsona. Of those, the later two are sort of mnemonic devices more than full-blown general-purpose writing systems, and the third was a semi-secret system that we today don't know the full secret of anymore. That leaves us only Merotic and Old Nubian from which we could derive any natively-recorded personal information that isn't mostly mythical.
The Merotic language has been extinct for 1700 years now, and isn't well-understood. Its still under debate if it was Afroasiatic or Nilo-Saharan, or perhaps an isolate. Given its geography, and the fact that its writing system required accounting for most vowels, I'd be inclined to lean towards the non-Afro-Asiatic theories, but AA wouldn't be completely unreasonable either.
Further complicating matters, one of the names I could dig up that we know from those sources was the king of an Afroasiatic people. Given its corpus, there exist oddles more, but I think these sources are still being worked (and in some cases still being found). There should be oodles of names in these sources, but they just aren't that popularly known at this time. For instance, the above link mentions a "Lady Maliwarase", and an "Adatalabe", both related to royalty.
Old Nubian was a successor system to Merotic, and is much better understood. It was an Eastern Sudanic language, with makes it either Nilo-Saharan or its own major language family, but either way not Afroasiatic. I had trouble digging up any specific names to give you, but as a large amount of the existing corpus is legal documents, it will certainly be full of local names.
