While I may take issue with some of the points in the OP, I shall try to answer your conditions faithfully.
In this ATL, for some reason Gaddafi, Saddam and Assad are running around with no war to remove them, there is no Gulf War, and Osama just simply never exists(no 9/11).
Al-Qaeda or some ATL analogue(henceforth shall be refered to as ATL Al-Qaeda for the rest of this post) would form in Afghanistan. Even without US troops in Saudi Arabia, the Islamists, who never really liked th US, would have come into conflict eventually with America because of the unipolar moment. However, this terror group decides to be more pragmatic and attack the secular and pro-Western leaders of Muslim countries. The theory is to establish a united caliphate, or at least Islamic front and that would aim to spread Islam to the rest of the world. In that regard, ATL Al-Qaeda would launch attacks in Tajikistan. Tajikistan had a civil war with Islamists in the 90s. The intervention results in the government being defeated and a new Islamist regime being set up.
ATL Al-Qaeda would also set us bases in the the post Soviet Caucasus breakaway states and in Bosnia. As a result of increased jihadi influence in Bosnia, Dayton never gets signed because the foreign fighters and local Islamists reject any proposal for a negotiated settlement with Serbs; their war only ends with the destruction of Republika Srpska. Eventually this leads to the Bosnian war to become a 3 way civil war, the Izetbegovic government, the rump remains of the VRS after NATO bombardment, and the Jihadis. This indefinitely prolongs the Bosnian war.
A series of assassination are carried by ATL Al-Qaeda in its mission of removing unfavourable leaders. Because of the instability nextdoor, Islam Karimov, the secular president of Uzbekistan, is assassinated and an Islamist government takes his place(Islamic Tajikistan invades to secure them). Another place where attacks are high is in Pakistan. Benazir Bhutto would be assassinated during her term in the 90s. Aside from the fact these people oppose ATL AL-Qaeda's agenda, they would hope by removing these people, often authoritarian, that the country would fall apart and they could step into the fill the vaccuum.
Or they would try to start an uprising. High on ATL Al-Qaeda's list would be Hosni Mubarak's Egypt and the King of Jordan(because both are friendly with Israel and the US).
Since 9/11 doesn't occur, there is no GWOT. Since there are no major attacks on targets outside Muslim countries, Putin probably allows the Caucasus breakaway states to exist so as long as they don't attack him. While Assad and Gaddafi would no doubt focus their attention on opposing jihadis. Saddam most likely would try to cut a deal with them in order to leave him alone. Saddam was never really a secularist, and throughout his reign Iraq drifted to Islamism. The deal is the Saddam effectively disinherits his son in favour for Izzat Ibhrahim Al-Douri as successor. Al-Douri was a strong proponent of political Islam inside the Ba'ath party so that makes a suitable candidate. Al-Douri however makes a secret independent deal with ATL Al-Qaeda, to effectively purge the Ba'ath party and allow jihadis influence in his government.
In the modern day of this ATL, several countries have fallen to the Islamic jihadis, though how many is up in the air. But definitely Islamism is far stronger than it is in the OTL. This is because ATL Al-Qaeda's campaign against secularists effectively intimidate many into not running for office, allowing Islamists freer reign.
ATL Al-Qaeda would be a priority for the US, and Russia. But without a GWOT, there won't be enough support to oppose them to the extent to curb their influence.