Looks like a huge revolt is brewing in the Labor party because of Blair’s insistence on going to war regardless of the will of the British people and the other Labor MPs. I heard MP George Galloway on the radio talking about getting rid of Blair. How easily could this be accomplished? Just by calling new elections for party leader and voting in a new party leader—who would then replace Blair as PM? Is overthrowing the leader of a nation really that easy?
I think Labour’s National Executive Committee would have to call an extraordinary party conference, at which there would have to be a vote (at least, that’s my understanding of a piece I heard on the radio yesterday). I expect that could happen fairly quickly, but I personally don’t think it will happen at all.
Bear in mind that in theory the Prime Minister is no different from other cabinet ministers - “first among equals”. Whoever leads the governing party becomes Prime Minister by default. There would be no need for a general election, since (again, in theory at least) the public vote for the governing party, not for a particular individual as Prime Minister.
In addition to Labour replacing him, (AFAIK) any member of Parliament could also put forward a vote of no confidence. If Blair lost, he wouldn’t have to go, but he would, and very quickly too. Most PMs wouldn’t want to face a VoNC if they thought they could lose, so he’d resign first.
Less formally, there could also be a cabinet rebellion such as Thatcher was threatened with: she resigned rather than face that. Blair would be replaced by another member of the Labour party, most likely from the current cabinet.
There are three ways in which this could be accomplished.
(1) Rebel Labour MPs set in motion the Labour Party’s internal proceedures for a leadership challenge. So far this is the method that everyone is assuming might be used, but there is also general agreement the rules are still stacked in Blair’s favour. To do this the rebels would need 20% of Labour MPs to ask the Labour Party Conference to call a new leadership election. More than 20% of the MPs are unhappy with Blair’s current policy, but one cannot assume that all of them will want to commit themselves to his removal. They know that this is a high risk strategy.
(2) A vote of no confidence in the Commons. This would be easier to organise but would also involve huge imponderables. For one thing, this would not necessarily remove Blair. The Conservatives might actually see advantages in voting for the motion or, more likely, not voting against, as they might prefer for the Labour Party to be left with a leader who was unpopular with his own side and who had been saved by them. Moreover, if Blair was defeated, he would still have the option of dissolving Parliament rather than resigning. Admittedly, this would amount to political suicide as it is difficult to see how he could win the resulting general election, but this is a useful threat which could be used to frighten would-be rebels.
(3) Senior figures within the party go round to No. 10 and persuade him that it is time to go. Claire Short or Robin Cook telling him that he ought to go wouldn’t make much difference, but if, say, Gordon Brown and John Prescott did so, it might be another matter.
I suspect Blair will only take career advice from Brown when hell freezes over.
First there is leadership of the Labour Party. Next there is the position of head of the government.
Each party has its own rules for (s)electing its officers; or dumping them.
However, it is the Monarch (technically) that invites someone to form a government. There is no rule that says that it must be the leader of the winning party. Indeed if any parliament was “hung”, the monarch would take advice and may invite a neutral person (but from one of the 2 houses of government).
Also note that ministers do not have to be elected MPs; they can be members of the House of Lord’s (e.g. Lord Carrington as Foreign secretary under Thatcher). It would be unlikely that the PM would not be an MP, otherwise he/she could not attend the House of Commons, but no actual rule specifically prevents it.
To elaborate on what Stephen_G has written,
Being the leader of the largest party is not automatically synomonous with being PM. Churchill became PM six months before becoming Tory leader. Equally losing the party leadership does not deprive a PM of his position - John Major resigned as Tory leader in 1995 and for a fortnight or so remained PM without being party leader until he was re-elected as leader.
If Blair lost the party leadership he would not cease to be PM - however, in practice he would immediately resign.
If there is a hung Parliament the Queen is unlikely to invite a neutral to become PM - by convention the Queen will firstly invite the leader of the largest party, if they fail to form a government, are defeated or indicate that they do not wish to attempt to form a government she will proceed to invite the leader of the next largest party. Only after this could she theoretically ask ANY other person to form a government who she believed would be capable of commanding a majority in the House of Commons. It doesn’t have to be an MP or a peer. It could be Joe Bloggs - though see below for how it would work.
Members of the cabinet don’t need to be MPs. Two positions, Lord Chancellor and Leader of the Lords, must be peers. Chancellor of the Exchequer and Leader of the Commons must be MPs. Any other minister can be a peer - the most recent case being, I believe, Lord Young in the mid 1980s (and prior to that Lord Carrington). When a peer is the head of a department he will have a junior minister from the Commons who stands in for him in the House of Commons and who will sit in the cabinet in a sinecure position, normally either Lord Privy Seal or Chancellor of the Duchy of Lancaster.
There are, as Steven says, no rules preventing a PM being a peer. Since 1923 when Curzon was passed over because he was a peer, it has been seen as convention that the PM must be an MP. In many areas conventions in the British constitution are binding - so while this rule is unwritten, it’s still a rule.
The Queen can still ask a peer to form a government - she could ask anyone to form a government - the only difference is that now the new PM would be obliged to get himself a Commons seat quicksmart. In 1963 Lord Home served as PM for four days as a Lord, then served as PM for three weeks as Sir Alec Douglas-Home as a normal member of the public without a seat in Parliament, before finally being returned to Parliament in a by-election.
As an aside, the Conservative and Labour party’s rules both state that a leadership candidate MUST be an MP. So under normal circumstances it is the rules of the parties that ensure a PM must be an MP, not the constitution.
(Oh, I understand Gordon Brown goes next door to ask when Blair is resigning regularly. If Brown publically said it was time for Blair to go, and other members of the cabinet agreed, I think he’s be toast 
I ought to know more about this, being my country. But blair is PM, not president - I don’t know what he can do without parliaments say-so, but I think if parliament votes on something that’s considered the final say.
Ain’t necessarily so. Most of the monarch’s Royal Prerogative is conferred directly on the Prime Minister. He doesn’t need to ask Parliament for this stuff. Because the UK monarchy isn’t really constitutional.
I don’t have a list of the things Blair can do without Parliament, but essentially there are two lots of things. Firstly there are powers that Parliament has granted to the government. Parliament has, for example, passed legislation allowing the Deputy Prime Minister to review planning applications.
More importantly in this context are the Royal Prerogative powers. These are the political powers of the monarch that are now exercised by the government on her behalf, most importantly to sign treaties and to declare war. It is through these powers that Blair would order troops into Iraq.
As regards the role of Parliament - it is to pass legislation. If Parliament rejects a Bill then that’s the final say (well - the government can have another vote, but you get the picture) .
On issues like the war in Iraq, the House of Commons is expressing its opinion. It doesn’t bind the government - the motion that the Labour rebels opposed last month was an amendment to motion noting resolution 1441. So theoretically such motions mean nothing and Blair can go against their opinion…however in effect, if Blair had lost the vote it would be politically difficult, if not impossible, to go against the will of the House.