I believe Himyar would expand because they were under similar conditions, or would fall into similar conditions at the very least, under Roman and Sassanid expansionism, and 200 years earlier would be a good start to stabilise the kingdom and make it powerful enough that it would eventually become similar to Palmyra, which used expansionism in order to curb Roman dominion and assert independence completely, not to mention that the Himyars would be the best vehicle for Arab unification against Roman and Sassanid tyranny. Muhammad succeeded because there either wasn't any stable government in the Arabia of his time (which was basically a tributary merchant state of Aksum) that could realise a rebellion, thus leaving him without competition to unify the Arabs, or the states that were stable and relatively powerful were vassal tributary states complacent with the Romans and Sassanids, like the Lakhmid kingdom for example.
As for Aksum, I think the Himyarites, like Muhammad, would realise that going against Aksum would be a mistake and ignore it. This is the reason why Aksum did not intervene at the time the armies of the first Caliphs were kicking everyone and everything in the face. A Himyar that searches for religious tolerance would naturally not be hostile to Aksum and even become, not allies, but still neutral states to each other.
While I see your reasoning for the opinion that the Arab expansion into other regions, is likely or at least possible in a scenario without Muhammad, and is an idea that I have expressed in the past, the particulars that you enumerate, are in my opinion, somewhat flawed.
1. "Similar conditions," The Himyari and other Yemeni states were most certainly not in the same positon as the early dar al-Islam in terms of geopolitical arrangements. Himyar was based upon trade of the Red Sea whereas the early dar al-Islam and Khilafah, was based entirely in the central and it arose from a culture and ethos that was that, that of the Hijaz and Nejd regions. These regions of the Hijaz and Nejd, differed from Yemen critically in terms of its culture and the positioning that it will likely take in geopolitical scheming. The geopolitical situations of the Hijaz lent themselves toward the conquest first, of the interior of Arabia and then into Yemen and finally northward into the Levant and Iraq. Yemen however, has no real need for the conquest of the Arabs to the north if in a strong position and would be unable to conquer the Hijaz or Nejd if weakened. The Nejd especially, would give constant headaches for a nation based in the extreme southward of the land of Arabia. Yemen itself, is with a fairly large population, mountains and deserts on all sides, naturally leans toward the monopoly of trade entering the Red sea from the East and south. Based upon the realities with which Yemen is centered, it would be possible that Himyar as a powerful Yemeni state, expands west and south into Africa to further monopolize its grip on trade and as part of the greater slave trade so greatly mentioned and lucrative in the epics of the Arab peoples.
Further, it is quite an oddity to compare the religious fervor with which the Arab armies of the dar al-Islam engaged the foes they faced to a 'tolerant Himyari Jewish-Yemeni state.' I also do not see how simply tolerating other groups leads to any benefit for the Himyar. A monarchy or clan that focuses itself upon trade benefits from diversity, as the coming and going merchants exchange goods freely and the tolerance of diversity, allows this to flourish more astutely. However, diversity is not a benefit to the expanding nation, especially the expanding nation that relies upon continuous victories, as the Muslim did and how Himyar would if they were to ever possibly face the Sassanids (I cannot imagine the Himyar actually resisting the Byzantines unless the Byzantines decide to actively support Aksum, which would in my opinion not lead to Byzantine-Himyar conflicts, but Byzantine support of East African magnates versus the Himyari armies). Further, such diverse armies would be inclined to infighting and bribes by the enemy. The Muslim armies of Umar ibn al-Khattab purged most dissent from their armies and in terms of religion and background, the entire forces were essentially copies of one another. Your, 'tolerant Himyar,' would not be, making it a diverse force unlike that of the Mulsim forces of the Khilafah.
2. "best vehicle for Arab unification," The idea of the Arabs as a single and unbroken unit of people has yet to arise and possibly only arose with Islam in the IX century. Yes, the Arabs were certainly a distinct group and one in which they made distinct from other groups, especially those of Africa, however, the idea that Yemeni would have any goals for the unification of Arabs is an anachronism. Further, the ideal Arab that we think of and are attempting to apply to Abu Kariba or Himyari Jews and what have you, cannot be applied. Traditionally, the ideal Arab so spoken of in the medieval texts is that of the Arab from the land of Nejd or the Hijaz and to an extent northern Yemen; not the land of Himyar to the far south, which like the land of Magan, was tied to the trade from the ocean as opposed to the origins of the Bedouin and the hard necessities of the desert and of a life of raiding and warfare.
This necessity of war and raiding, lent itself to the ideals and Islamic concepts of jihad and ghazw (struggle and raiding). These to my view, contributed to the success of the Arab armies initially in their conflicts with the Sassanid and Byzantines.
3. The question of Aksum you raise, I disagree with. I doubt for one, that the early Islamic state avoided the kingdom of Aksum out of fear. There is nothing in the Islamic record to suggest this. The only suggestions that we have is that the Early Muslim considered the Aksumite ruler, Najashi to be Muslim or at least a Christian with certain truths and or proofs (scholars disagree on which it was within the fiqh of Islam). Further, it is suggested by the ulema that Najashi implemented the laws enumerated in the Torat and Injil, in their pristine sense. Thus, the ulema reason, for why jihad was not placed upon Najashi, was that he was not causing fitnah (mischief) in the earth by the practice of laws that were revealed by Allah in the past. As in the more correct sense of jihad in the physical sense, war is to be made against all who do not practice the sharia with which Allah has enjoined upon all humanity. Additionally, some argue that Najashi had a pact of submission and protection pact with the Muslim, which I personally do not agree with. It is my opinion that the previous view, that it was believed by the early Muslim, that Najashi practiced a form of law form previous scripture that the Muslim reasoned was permissible and war with them was not permissible.
4. The idea that the Sassanids or Byzantines were tyrants in the modern sense that you use the word, would be incorrect. Though, I am not understanding what you mean by this. Could you elaborate on this tyranny of the Sassanid and Byzantine. Either I am unaware of Byzantine-Sassanid interference in Arabia of the time or you are referencing the term taghoot or taghwaheet (those who transgress the limits or a tyrant) in Islamic jurisprudence. Which is it?