As has been mentioned before; even though the Maltese are effectively Roman Catholic Arabs and speak a language that several linguists consider an Arab dialect, they do not regard themselves as Arabs, so they do not count in this challenge.
That said, if you would create a scenario in which the Maltese for some reason
do keep regarding themselves as Arabs, then that would count.
Before the Muslim conquest, the regions now known as the Maghreb had some of the largest Christian populations in the former Western Roman Empire. Would it be that much of a stretch to imagine that the Berbers would hold on to Christianity and eventually fight off Arab overlordship? (It's a genuine question, I'm not enough of an expert on the period to know the answer).
That's actually quite possible - many Berber tribes and tribal confederations fought the invading Muslims, and not without success.
The campaigns of
Kahina are a good example of this.
And Byzantine Africa also put up a good fight againest the Muslims, since it took them about forty years to capture Carthage and the rest of Byzantine Africa, even though Byzantine Africa was practically left to fend for itself.
And Christianity indeed did have a good number of adherants among the Berbers (the more or less Romanized Berbers in the lowlands and coastal areas, that is. Most Berbers in the mountains, desert, and the area west of Gibraltar were still pagan or Jewish at this point), and a more coordinated Berber resistance could certainly have halted Muslim expansion to the west.
However, the biggest problem with this scenario is the Catholic-Donatist conflict that was raging among the Christians in Byzantine Africa at this point.
This conflict weakened and deeply divided the Christians in North Africa, and the schismatic and effectively anti-papal Donatist movement merged with local anti-Roman political movements.
The result was a religious-political conflict that had reached its peak at about the point that the Muslims invaded Byzantine Africa.
..
If this conflict would have been resolved somehow prior to the Arab invasion, then Byzantine Africa and the local Berber tribes could certainly have halted Muslim expansion, or they could at least have delayed it for centuries instead of decades.
And if Muslim expansion would have been stopped (or at least halted for a few centuries) in the area of modern Tunesia, then the Berbers of the mountains and the area of modern Morocco, who were
at best only superficially Christianized, would have been exposed to Christian influence for a few more centuries.
And with a little luck, Christianity might just gain a firm foothold in the area, and that would only contribute to Berber resistance to possible Muslim invasions and Arab Muslim overlordship.
Would have been quite possible. However, if the Berbers and/or other pre-Arab groups in N Africa successfully threw off Arab domination, especially early on, they couldn't really be described as Arabs could they?
Technically you're right, but we wouldn't let such minor details get in the way
of discussing interesting possebilities and scenario's, now would we?