Al-Qaeda called for fresh attacks against US targets in the Arab world and the West, as Washington said it was pulling non-essential embassy staff out of Sudan and Tunisia.
Al-Qaeda in the Arabian Peninsula (AQAP) also called for more violence against US diplomatic missions in the Middle East and Africa, and urged Muslims in the West to attack US interests, SITE Intelligence Group said.
The US State Department ordered all non-essential personnel to leave Sudan and Tunisia following embassy attacks over an anti-Islam video, warning US citizens against travel there.
Hours earlier, Sudan had refused a US request to send in special forces to protect the Khartoum embassy, after protesters attacked it on Friday.
In cities across the Muslim world protesters have vented their fury at the US-made film "Innocence of Muslims", targetting symbols of US influence ranging from embassies and schools to fast food chains.
As US investigators questioned the man allegedly behind the low-budget movie before releasing him, the top Sunni Muslim authority called for a worldwide ban on all forms of attacks on Islam and other religions.
Federal authorities questioned Nakoula Besseley Nakoula in Los Angeles, trying to establish whether he had broken the terms of his probation over a bank fraud conspiracy, Los Angeles County Sheriff's Department spokesman Don Walker told AFP.
In the worst violence triggered by the anti-Iswlam film , the US ambassador to Libya, Chris Stevens, and three other Americans were killed late Tuesday when suspected Islamic militants fired rocket-propelled grenades at the US consulate in Benghazi.
AQAP, Al-Qaeda's Yemeni offshoot, did not claim direct responsibility for the attack in the eastern Libyan city.
But it said the killing of Al-Qaeda deputy leader Sheikh Abu Yahya al-Libi in a drone strike in June "increased the enthusiasm and determination of the sons of (Libyan independence hero) Omar al-Mukhtar to take revenge upon those who attack our Prophet," according to SITE.
"May the expulsion of embassies and consulates lead to the liberation of Arab lands from the American hegemony and arrogance," it said in another statement.
It was a duty for Muslims on Western soil to attack US interests, it added.
In Afghanistan, heavily armed Taliban stormed a strongly fortified air base in Helmand province where Britain's Prince Harry is deployed, killing two US Marines in an assault the militia said was to avenge the American-made film.
The attack came after at least 11 protesters died as police battled to defend US missions from mobs in Egypt, Lebanon, Sudan, Tunisia and Yemen.
US Defence Secretary Leon Panetta said Washington was configuring its forces to be able to cope with widespread violence.
"We have to be prepared in the event that these demonstrations get out of control," Panetta told Foreign Policy magazine.
Already the US has deployed counter-terrorism Marine units to Libya and Yemen and stationed two destroyers off the North African coast.
But Sudanese Foreign Minister, Ali Karti, flatly rejected a US request to send special forces to protect the Khartoum embassy, the official SUNA news agency said Saturday, quoting his office.
Hours later, US officials announced it would evacuate all non-essential staff and family members from Sudan and Tunisia.
On Friday, guards on the roof of the Khartoum embassy fired warning shots as protesters waving Islamic banners breached the compound, having earlier ransacked parts of the British and German missions in the Sudanese capital.
In the past week, US embassy compounds have also been breached in Egypt and Yemen, whose parliament rejected the presence of US Marines, although the government has already accepted them.
The head of Libya's national assembly, Mohammed al-Megaryef, said foreign elements may have been involved in the "meticulously executed" attack on the US consulate in Benghazi. It came on the anniversary of the September 11, 2001 attacks on the United States.
In Friday night's attack in Afghanistan, the assailants penetrated the air base and damaged aircraft.
Military spokesman Major Adam Wojack said 18 insurgents were killed -- including a suicide bomber. Prince Harry was never in danger, officials said.
Police in Sydney fired pepper spray to contain protesters trying to enter the building housing the US consulate, as hundreds also demonstrated in Belgium, France, Israel, Indonesia and the Maldives.
In Somalia, the Qaeda-linked Shebab militia, which controls large swathes of the country, called on Muslims to launch revenge attacks on Western targets.
President Barack Obama urged Americans not to be disheartened by images of anti-US violence, expressing confidence the ideals of freedom America stands for would ultimately prevail.
In Cairo, the grand imam of Al-Azhar, the highest seat of Sunni Muslim learning, called for an international resolution banning all forms of attacks on Islam and other religions, in a letter to UN chief Ban Ki-moon.
The resolution should "criminalise attacks on Islamic symbols and on those of other religions, after the violence against those who provoked challenges to world peace and international security," Sheikh Ahmed al-Tayyeb said.
Der Spiegel news weekly reported that far-right group Pro Deutschland wanted to screen "Innocence of Muslims" in Berlin.
Germany Interior Minister Hans-Peter Friedrich told the weekly he would do everything in his power to stop them.
