Without 9/11, there would be no Bush doctrine. But there might still be the terrorist attacks in Bali, Djerba, the Moscow theatre siege and the Beslan massacre. It would be strange to see the European, Russian and Asian reactions to this without the Bush doctrine. Possibly Putin will declare something like a "war on terror" with a more open anti-Islam stance (regarding the situation in Chechnya in the early 2000s).
A curious case are the Madrid and London bombings. It is generally believed that those cities were chosen for Spain and Britain's participation in the Iraq war, which might not have happened without 9/11. So instead of chosing those cities, terrorist might try it somewhere else.
Instead of Huntington's "The Clash of Civilizations", the more popular books would probably be Oriana Fallaci's "The Rage and the Pride" (also a bestseller in OTL) and conspiracy stuff like Bat Ye'or's "Eurabia", because they focused on the European situation. The anti-Muslim right-wing parties might even be more popular, as they would point out that Europe, not America, is vulnerable to Islamic fundamentalism.
Without the Iraq and Afghanistan wars, the situation in the Middle East would also be very different. Would the Taliban fail, like the Hasan al-Turabi-influenced Islamist regime in Sudan, or would they become an early version of ISIS, including imperial ambitions? In Pakistan, Musharaf's regime would be much less stable without American support, possibly leading to another war after the New Delhi attacks of 2001. Ghadaffi probably would gamble a bit more with his own nuclear program, possibly making him (and not Saddam) the US' main enemy. I also think that without the "axis of evil"-speak, Israel and Syria might have a better shot at negotiations. After all, they became very close in 2000.