Newly appointed Gordon Brown is Scottish and a member of the Church of Scotland, not the Church of England like Blair. Have there been any other Prime Ministers from outside the Church of England? Even the first Jewish PM, Benjamin Disraeli, was an Anglican.
Wikipedia has Margret Thatcher listed as Methodist.
I think John, Earl of Bute, was Church of Scotland (early years of George III’s reign, FWIW).
It’s rumoured Blair may be converting to Catholicism now that he’s left office. So at least in belief he may count himself.
Previous thread on a similar subject.
Another example of someone whose religious loyalties are quite difficult to pin down. Don’t assume that he was probably a member of the Church of Scotland just because he was Scottish, as eighteenth-century Scottish aristocrats were more often Episcopalian, especially if they were as anglofied as Bute. Moreover, Bute must, at the very least, have been willing to conform to the Church of England, if only in order to fulfill the sacramental requirements of the Test Acts. The Scottish exemptions to the English Test Acts applied only to those holding offices in Scotland, not to those Scotsmen holding offices in England (or throughout Britain as a whole). Even at the time, this was recognised as a bit of an anomaly.
To answer questions raised and unanswered in that past thread, Ramsey McDonald was Presbytarian/Free Church of Scotland, and James Callaghan was a Baptist.
Now, when they get the first Hindu, Pagan, or Shinto PM, that’ll be news. 
(Does the PM have to be of any defined religion?)
(Re: Disraeli: How can someone be Jewish and Anglican at the same time?)
“Jewish” doesn’t necessarily mean of Jewish religion. It is also considered an ethnic label. If your mother is Jewish, so are you, even if you become a Christian or a Muslim or whatever.
In Disraeli’s case, he was baptized shortly after birth into the Anglican church. (Supposedly it was an act of spite by his father who was in a quarrel with a local synagogue.) I believe he also identified himself as Jewish, but I’m not that familiar with his personal religious pratices.
An apocryphal riposte by Disraeli, when he was blasted by an antisemitic MP of Irish descent: “Yes, I am a Jew, and when the ancestors of the right honourable gentleman were brutal savages in an unknown island, mine were priests in the temple of Solomon.”