If the Israeli pre-emptive strike had not destroyed most of the Arab nations' air forces on the ground, could they have won in 1967?
Not really. Less successfull beginning of 1967 War for Israel would mean that it's Air Force will be tied in battles with Egyptian and Syrian AFs (Jordanians didn't have much to speak of) and would be unable to support it's ground forces as "super-long range artillery" the way it did IOTL. That means that Israeli will be waging defensive battles against advancing Arabs. Tough and bloody business it will be, but (taking into account that every single Israeli believes that inevitable and most painful death of him/herself and family would be an immediate consequence of lost war) Arabs are not able to deal with Stalingrad 50 miles wide and 200 miles long.
I think 1948 is the best possibility for an Arab victory.
Yep.
Well, I don't know if it's really possible for the Arabs to win that war, in the sense that they retain all of Palestine.
It would be a tough call but it is IMHO doable.
If you could get political developments in the Arab world to go some other way it's possible that eventually you could get the Arab world dominated by governments aligned with the US. Nasser's Egypt really set the tone for what went on elsewhere. I think if you could replace Nasser with a non-socialist who allied with the US you could really change things throughout the Arab world.
Nasser spent first half decade of his rule loudly banging his head against American doors in futile attempt to get their support for Egypt modernization program. Unfortunately, Americans could not support such an abomination as wogs trying to lift themselves out of medieval misery (root cause of many US-Indian problems too). So, in the late 1950s he started to fashion himself as socialist.
Bonus points if Israel can be somehow more Soviet aligned, or at least more neutral in the cold war. Perhaps by changing early Zionist/Israelli politics such that the socialists are more dominant and Israel is sort of like India was, a Soviet aligned leftist democracy.
You mean, like Soviets giving Israel a lot of stuff it could actually use (whatever Soviets were, skimpy with their client regimes they were not) would result in Arab victory? Like "Arabs in Shermans or M48s beating Israelis in T-54s"? Well, I would like to see an explanation of this idea.
As I said, 1948 is the best Arab chance ever. How could Arabs win in 1948? One way is to make them modernize earlier. But this creates famous contradiction "in order to successfully fight us you need to become us and then you don't want to fight anymore". However, set of small steps to weaken Yishuv (Jewish community in Palestine) and strengthen Arabs could lead to eventual carving of British Palestine between Egypt, (Trans)Jordan and Syria, which will likely be accompanied by a significant bloodletting, but not outright killing of 100% of Palestinean Jewry.
Lets start with weakening Jews.
- kill Ben Gurion. Guy almost dripped charisma and he was single uniting force for warring fractions and warlords (and number of Palmach and Irgun commanders can be called warlords without stretching truth too much) in Jewish community. Without Ben Gurion old wounds between Palmach and Haganah (special forces and "army", as much as "army" moniker can be used for Haganah), Haganah and Histadrut (military and civilian wings of Left), Left and Revisionists, secular and religious communities are bound to rupture, likely swallowing any semblance of organized resistance and reducing Jewish self-defence to a number of village gangs fighting for survival (dealing with those gangs still would not be easy).
- Make USSR seriously hostile to the idea of Jewish state. IOTL USSR wasn't truly an ally, but they allowed Czech purchase and often looked the other way when Zionist groups conducted recruitment compaign among Jewish army vets from Lithuania and Poland (pre-WWII Poland, which included half of today's Ukraine and Belarus). Czech weapons were crucial in securing Galilea and stopping Egyptian push toward Tel Aviv. They will likely be partially replaced by another sources of weapon procurement ITTL, but not 100% and heavy weapons (fighter planes and mortars) are largely irreplaceable. EE army vets were absolutely crucial in creating Israel's armoured units (1st tank company of Israel Army had been known as "Russian company" and Russian was the official communication language of this unit).
- Dispatch special task force of AH butterflies to get rid of several particularly successfull Mahalniks. Mickey Markus (aka "one who kept Jerusalem for Israel") and Ben Dunkelman (who gave Lower Galilee to Israel) are coming to mind first and foremost.
Now, what can be done (piecemeal) to increase Arab's ability? One can dream of Titanic figure to beat all Arab regimes into submission and coordination of their efforts (feat not achieved since times of Prophet, I would dare to say), but this isn't too realistic. War effectiveness of every Arab force can be moderately enhanced, but not their coordination. And the main source of enhancements appears to be use of foreign "advisors" (mostly ex-Nazi and Nazi collaborators), as Arabs didn't truly suffer from lack of equipment they could use with available manpower.
- There's not much what could be done for Jordan. Abdullah played his hand (small but well-trained force with no possibility of reinforcements) pretty good. His army was effectively under British command, so not much chances to recruit Nazi for the Legion.
- Syrians did use "advisors" (some army officers, some air force pilots), but not too extensively. They could easily create something like "foreign legion" of several hunderds battle-hardened Axis veterans, and such a force would be absolutely devastating. IOTL Israel hung on by fingernals when Syrians attacked Degania, but only thanks to simple fact that Syrian tankers and supporting infantry units were absolutely inferior.
- Mufti's Arab Liberation Army could benefit enourmously, not from German military advisors (cultural distance is too great), but from somebody experienced in modern small-scale war and in management of tribal levies. No shortage of such figures among North Caucasian, Bosnian or Tartar Muslim Nazi collaborators, all of whom were on the run and would be glad to work for the Mufti.
- Egyptians were under close British monitoring too, so not many chances of "Nazi Legion", but some advisors in force attacking Tel Aviv could break the IOTL chain of events and give much of Coastal Plain to Egypt.