I wouldn't count the Palmyrene Empire as Arab, they were based in the non Arab Syria, which in general was Aramaic with some Arab immigrants. However in a similiar time period we have the Tanukhids, Ghassanids and Lahkmids as major forces in northern Arabia. None of these had the ability by themselves to conquer either nation. Essentially, an Arab state needs the (in the context of Arabia) seemingly endless manpower of Yemen and the warrior culture prevalent throughout the Najd mixed with North Arabians (Lahkmids and Ghassanids). These combinations facilitated the Arab conquest, not even counting things such as Arab battle techniques such as duels which caught the disciplined and Sassanid and Byzantine armies off guard.
But, Islam as a religion I would say is not necessary to create a unified Arab movement conquering vast areas to the north. A great warlord on the level of Attila or such could rise and unite the Arab tribes for a time who could conquer vast amounts of land and then integrate into the systems the conquer. I could definitely see someone like Musaylama rise up and do the same conquest without a unified religious code. In essence, it is surprising that Islam was successful in its conquest since it taxed people who had never been taxed and greatly endangered its ability to effectively wage war against Byzantium and Sassanids.
If we go REAL early we could try the Qedarites lol.