The old adage has it that British prime ministers are either vicars or bookmakers. In Phoney Tony the country has a bookie masquerading as a vicar, a posture that does little for the standing of either profession.
-- Glen Newey, LRB, 2003
There are a few other mentions on the web of the form "Prime Ministers are either bookies or vicars", but not much that gives detail on earlier usage or how old it might be. I'd guess it is an older quote or saying that predates the web. Can anyone share an origin, or failing that, earlier examples?
EDIT with more detail on research: Initial searches for the phrase on the web show very little. With the tip from @peterG that the variant "bookies or bishops" was more common, this led to an Anthony Crosland biography mentioning Hugh Gaitskell, and then to a thesis by Shack (PDF) p277 citing Muggeridge's book. This seemed solid enough to result in my answer below.
@JEL has since found Curran in 1956, predating it, in his answer.
Peter Hitchens suggests Alan Watkins in his Daily Mail column in 2017. This is technically possible as he would have been 23 in 1956, but not the greatest source without further support.