The PM doesn't have to be the leader of a party - but he/she usually is.
In 1995 John Major resigned as leader of the Conservative Party, but stayed as prime minister during the time when a leadership election was held (and he was re-elected as party leader).
Neville Chamberlain was forced to resign as PM in May 1940 because his government was strongly criticised during a debate in the House of Commons, and Churchill became PM. But Chamberlain continued as leader of the Conservative Party until October 1940, and resigned from the position only just before he died.
Originally, Tony Blair said that he would serve a full third term as PM but not fight a fourth general election. It is conceivable (but unlikely) that he would resign as party leader, allow the new leader to be elected, and stay as PM for a few months before a general election before resigning as PM.
Constitutionally, the convention is that the Queen should invite to become prime minister whoever is most likely to be the leader of a majority in the House of Commons. In some other countries, such as Italy or France or Japan, it is very common for a prime minister to be appointed who is not necessarily a party leader; such a thing could happen in the UK, particularly if there was a hung parliament and a need to find a prime minister who is acceptable to other parties.