Arabic, of course, would still be spoken in various parts of the region, and might even slowly replace Aramaic in some areas even without the early Caliphate conquests, as it was seemingly an ongoing process before Islam. "Arabic" might not be the name under which the language is mostly known today, and without the unifying force of Islam, it would likely fracture into divergent varieties pretty soon (also an ongoing process IOTL of course).
Aramaic in its multiple varieties would, however, remain the primary spoken and, increasingly, written language of the settled parts of the Levant and Mesopotamia, including some adjoining highlands, for longer. If, where and when a form of "Arabic" overtakes it is a matter of specifics in the future of the TL, but even in that case, in all probability it would not be a complete substitution (which did not happen entirely even IOTL).
Also, a Medieval form of Sabaic-like South Arabian has more chance to survive both as a spoken and written language in a no-Islam TL, even if Arabic was already expanding in the area as well (ironically enough, seemingly in part as a vehicle of Christianity). In Dhofar and surroundings, the ancestor of Modern South Arabian was probably already spoken and, since these languages were not replaced by Arabic IOTL, it would likely continue to do so.
God knows what was spoken in pre-Islamic Oman, but probably Arabic would dominate the area ultimately.
The "Hasaitic" language of the Gulf Coast (which we don't know for sure was still spoken at the time, some Syriac documents note a "Qatari" language still spoken that may have been its continuation) may or may not be replaced by Arabic, I think it would.
I suppose that the North Arabian, presumably non-Arabic dialects transpiring from many of the so-called "Thamudic" had been aleady replaced by Arabic in most of the Peninsula, if they were distinct from it to begin with (no-one is really sure yet). If not, some of these may survive in this scenario, but I'm skeptical.
Kurdish and other non-Persian Iranian languages would, of course, be spoken in the highlands (alongside Armenian and Aramaic in some places).
Of course, Egypt would speak Coptic (and Greek among the urban elites).
The rest of North Africa, overwhelmingly, Amazigh languages, except coastal Tunisia and some other urban areas where African Romance is likely to survive (longer, at least). Punic enclaves may have survived into the seventh century, the future does not seem bright but who know.
It's hard to project much, however, without clearer specifications and political context. Turkic speaking groups are going to enter the region, but they might not leave the same huge linguistic imprint (this happened mostly from the eleventh century IOTL, but some presence is obviously earlier).
Almost certainly, nobody anywhere spoke Hebrew as a first language in late Antiquity anymore.