Who gets to go first?
The question of who gets to try to form a Government first after an election is not completely clear.1 Parliamentary conventions, using the 2010 Cabinet Manual, state
The question of who has the first opportunity to form a government is subject to differing views. The traditional position is that "the constitutional conventions on government formation (including in situations of a hung Parliament) were and are, firstly, that the incumbent Prime Minister has the first opportunity to continue in office and form an administration".
The draft Cabinet Manual chapter states that "An incumbent Government is entitled to await the meeting of the new Parliament to see if it can command the confidence of the House of Commons". The December 2010 Cabinet Manual adds the phrase "but is expected to resign if it becomes clear that it is unlikely to be able to command that confidence and there is a clear alternative".
If this is followed, then after an election, a Government can, if it wants, attempt to see if it can retain confidence in the Commons. If it cannot, it is expected to resign if another group can form a Government. Therefore, it would seem that whoever had a Government before the election - whether it be this majority party or another party, now with a minority - could get a crack at forming a Government. If not, someone else will take a turn.
The reason this is important here is that if this majority party cannot gain confidence, then there's no reason for the incumbent Government - if they are now a minority - to step down just yet if they still have reasonable support. It seems likely that they would want a shot at this, since there's no point in giving up control if nobody else can take it yet.
Maybe they'll gain confidence. However, it's more likely that they won't, and then we have a situation a little reminiscent of a hung Parliament. Some believe that the party with the most votes should get a first chance, in which case this now-majority party would definitely try first, even if it did not previously have a majority. If it was not successful, then again, we would see other groups try.
I can see two things happening:
- The majority party forms a coalition with another party - not to gain a majority (they already have that), but to attempt to gain confidence in Parliament. It's possible that the head of this second party could become Prime Minister. This would allow the majority party some control; it might be a better alternative to not having a Government.
- A party attempts to form a minority government. This is actually quite possible. Again, if the incumbent Government is a minority, they may try this.
- Someone other than the party leader could attempt to head the Government, if the party were to somehow agree to this. (This answer noted that the Queen does have a say in things; this linked document says that in the case of a hung Parliament, the Queen could meet with party leaders to discuss a coalition or a non-leader becoming a Prime Minister.)
These do have chances of succeeding. The chances aren't great, but they're chances nonetheless.
If someone goes to the Queen with a majority of confidence, then she will almost surely assent. If not, then there will likely be more talks until some agreement is made. The Government will then attempt to pass the Queen's Speech. If it fails, it may have to resign, and a new Government would try to form.
The upshot of all this is that if the party cannot form a Government, then we have a situation where anyone can try to form one. Parliament can reject a Prime Minister so unpopular that he or she would prevent a party from taking power simply by virtue of the fact that he or she could never form a Government.
In the meantime
By the way, while a new Government is being formed, whoever is currently in power will remain in power (unless they have lost their seat) - and in fact, the incumbent Prime Minister may be expected to stay on until a new one can be found. The Manual states
The incumbent Prime Minister is not expected to resign until it is clear that there is someone else who should be asked to form a government because they are better placed to command the confidence of the House of Commons and that information has been communicated to the Sovereign
1 This is the accepted convention, but some say that the party with the most votes should get the first chance. In the scenario you've devised, this would all be put to a test. Nobody really has a good shot here.