I do think missionary work would be the best way - at least to introduce it. However, to solidify it, you may need to do more.
A more... extreme PoD would be a recent love of mine : Exiled Belisarius, essentially an Exile campaign to remove a too-successful general to an extreme location. That'd almost certainly lead to attempts to convert Somalia.
A more practical PoD is likely to be the Missionaries, but combined with a Christian-backed faction rising to power. (i.e. Aksum and Constantinople backing a Somalian leader who had converted, with materials, money, and even men if needed) Military unification of Somalia that way could expand the Roman-influenced world on one hand, but also Christianise it strongly - and vitally, unify the city states.
What is interesting to me is that a united Somalia is a major trade powerhouse, likely to compete with the Arab world, that is also a useful ally against Persia. If we assume that this doesn't butterfly away Islam - then it also creates a very powerful ally against the Caliphate when it makes its moves, through effectively cutting off any trade from India, with force, recognising the value of Roman trade, and that the Arabs wouldn't NEED Somalia in the same way, making it entirely possible that Somalia would be a vital component to allow the Romans to effectively maintain control over Egypt and Syria with Somali and Aksumite help - with Somalia cutting off trade and potentially assisting the Aksumites in effectively raiding Arabia (if Aksum gets involved). I mean, the Caliphate having to protect itself from raids on Mecca, Muscat(?) by a Roman ally with every incentive to end Arab competition in trading with the Romans? That isn't an insubstantial distraction, and could even be enough to overwhelm the Caliphate.