In his Manifesto for an Enlightened Islam (Manifeste pour un islam des lumières), Chebel puts forth 27 proposals for extensively reforming Islam. He turns to the values of the 18th-century European Enlightenment for guidance, when rationalism and secularism guided the drive towards cultural, social and political progress. Chebel's first two propositions set the principles of reform: a new interpretation of the Koran, and the preeminence of reason over creed. However, he dismisses atheism, noting that "nothing very important is achieved outside the framework of religion." 
Chebel calls for putting an end to violence in the name of Islam; for renouncing Jihad, which is, in his eyes, immoral; for abolishing all fatwas calling for death; and for abolishing Islamic corporal punishment. Chebel stands against female genital mutilation and for banning slavery and trafficking in human beings in the Arab world; for strict punishment of the perpetrators of honor crimes and for promoting the status of women.
Most of Chebel's propositions deal with politics: He advocates an independent judiciary, the preeminence of the individual over the Islamic nation, and the struggle against political assassinations in an effort to promote democracy in the Arab world. He also advocates fundamental cultural changes, such as turning freedom of thought into a Muslim value, renouncing the cult of personality, respecting the other, and fighting corruption.
His other propositions address technology, bioethics, ecology, and the media. The last one reaffirms the preeminence of human beings over religion. Chebel's propositions aim at providing keys to a modern, reformed, enlightened Islam.
With regards to separation of church and state, the state will only reform when it sees a threat. That threat has now been recognized in the form of terrorism. Saudi Arabia is moving toward reforms to minimize the terrorism threat.
Country Terrorism Report: Saudi Arabia
Saudi Effort Draws on Radical Clerics to Combat Lure of Al-Qaeda
Saudis to Clean Up Libraries
In addition, effective reform must also come from the people.
Learning to Think and Tolerate Differences in Saudi Society
Saudi Human Rights Organization
Why must we fight?
Part of me died when I saw this cruel killing.
*Update* Atwar Bahjat Beheading Video a Hoax
Islamism and Terrorism 1
"Allahu Akbar" Indeed at All Things Beautiful