The Church’s loss is the world’s gain.

There are not many brave enough to take the risk of starting a new life at the age of 66. When Richard Holloway resigned as bishop of Edinburgh in 2000, he was turning his back on an institution that had shaped him since he was 14, when he left his home in a small town in the west of Scotland called Alexandria, for Kelham Hall, an Anglican theological seminary in the Midlands that trained boys from impoverished backgrounds for life in holy orders.

The decision he made to quit the Church was the result of a lifetime of following the path of courageous doubt. Welcoming gay people to his church, he came up against the morbid preoccupation with sexuality that has tainted Christianity ever since Paul invented the religion from the Jewish charismatic movement that had grown up around Jesus and Augustine interpreted the biblical myth of the Fall as having to do with the sexual origins of sin. When he heard of the wretched fudges that were being made with those in the Church who would not deal with women priests, Holloway burst out, "Oh, the miserable buggers! The mean-minded wee sods!" In an exchange he had with the archbishop of south-east Asia in the lavatory at Cumberland Lodge in Windsor Great Park, during a meeting of Anglican primates when he was still bishop of Edinburgh, Holloway was accused of filling hell with homosexuals because he was giving them permission to commit a sin that damned them to eternal punishment. "I resisted the impulse to deck him," Holloway writes, "and left him to go on pissing his wormwood and gall into the Queen's urinal."Amen to that

While Holloway's response to religious bigotry has been admirably forthright, his thinking on religion itself is searching and subtle to the last degree. His life has taught him that the ideas of belief and unbelief in terms of which religion is promoted and contested are not to
be taken on trust:

The fundamental difficulty is that all religious systems and the claims they make for themselves are as fragile - and sometimes as beautiful - as the floating villages of the South China Sea. The word faith is the giveaway. The opposite of faith is not
doubt, it is certainty.

The adamant conviction of believers - and unbelievers - is not what it seems to be. Citing the writer and psychotherapist Adam Phillips, Holloway sees certainty as a form of self-medication against the disturbance of thought. "Supreme conviction is a self-cure," Phillips writes, "for an infestation of doubts." A radical version of agnosticism - Holloway's preferred position - means living with doubt. "Strictly speaking, agnosticism should not be described as an hypothesis, because it is not so much positing an answer but learning to live without one."

Holloway's objection to religion is not to the beliefs it involves - unlike evangelical rationalists, he is happy to leave people believing whatever they like as long as they can't inflict their faith on others. But he rightly rejects the claims of religious institutions to define and possess the truth: "Religions may begin as vehicles of longing for mysteries beyond description but they end up claiming exclusive prescriptive rights to them."

If any specific event led to Holloway's departure from the Church, it may have been his book Godless Morality (1999), which sparked sharp condemnation from the then archbishop of Canterbury, George Carey. Whether he would have stayed if the Church had been less closed-minded is doubtful.

The view he has reached of religion as a body of myths has been articulated by a number of Christian thinkers and forms part of a theological debate that mirrors controversies about realism and relativism in the philosophy of science. But Holloway's inquiring mind was never going to be boxed into any orthodoxy and it was inevitable that he would eventually make the break. Since he did, he has been active in many fields and has produced a stream of books, including a penetrating inquiry into the nature of evil, Between the Monster and the Saint (2008). The Church's loss has been the world's gain.

No one reading this arrestingly candid memoir can doubt that Holloway's life has been driven by an authentic religious quest. Yet, all along, he had what he describes as "that wee man" - his reflective, questioning alter ego - perched on his shoulder. For many years, he seems to have felt that he simply wasn't up to the vocation he had undertaken. It was during years spent in Africa in the late 1950s, working as secretary to the newly appointed bishop of Accra, that he came to realise "what a disappointment I must be to God". At the time, he writes, it never occurred to him that he might end up in the priesthood.

He tells in humorous and touching detail of his early sexual experiences and resulting guilt and the enduring division he felt between his profession as a priest and his needs and desires as a ordinary human being. Describing one of several spells in the US (where he met his wife), he recalls serving as rector in an elegant part of Boston, where he "got used to gay couples coming to see me to discuss their flagging sex lives, though I doubt if I was ever much help at restoring their early ardour for one another".

Holloway mocks an experiment in speaking with tongues he tried during a period of spiritual emptiness, which resulted in him thinking for a time that he might be speaking in Mandarin - a theory he tested when, after practising his new-found fluency on a train back to Edinburgh, he unleashed a burst of the strange language on to a Chinese-looking woman, who fled through the station exit on to Waverley Bridge and off into the city. What he calls his "Janus-headed mind" and an unsparing sense of the absurd gave him a sense of self-division through all his life in the Church.

Leaving Alexandria is a profound, personal investigation of the virtues and flaws of religion and the most stirring autobiography I have read in a great many years. It is also a meditation on the nature of one's own identity. At the end of the book, when he considers what may be the most important lesson he has learned from his life, Holloway mounts a more fundamental challenge to Christianity than any that has been posed by the so-called new atheists.

Reflecting on his past during the hill walks he has always loved, he has come to see that the belief that we author our lives through our choices - which is central in Christianity in the form of the idea of free will and reappears in liberal humanism as the notion of personal autonomy - is an illusion.

A friend working on ancient Norse gave Holloway the clue in an essay she sent him on the metaphor of weaving in thinking about human life: "Norse mythology showed me that the way we act does not so much make us as reveal us; our response to circumstance shows us not what we want to be but what we actually are. I was never constituted to be a saint. I had just fallen among saints by accident."

John Gray is the New Statesman's lead book reviewer. His book "The Immortalisation Commission: the Strange Quest to Cheat Death" has recently been published in paperback (Penguin, £9.99)