Background
There are three positions in the line of succession where candidates must be eligible to be president:
- President.
- Vice president.
- President pro tempore of the Senate.
President should be obvious. Vice president is a little clumsily stated, but the general rule is that a vice president is just a president waiting to happen. The President pro tempore of the Senate has two duties:
- Presiding over the Senate when the vice president is not available and there is no other person delegated with that power. This is almost always handled by delegating that power.
- Taking over in the case that the president, vice president, and Speaker of the House all become incapacitated.
As such, choosing a President pro tempore of the Senate who is not eligible to be president would be silly. It's a post with a few ceremonial duties that can be delegated and one responsibility that cannot. Choosing someone incapable of fulfilling the one responsibility may be legal but it makes no sense.
So as a practical matter, these three positions are always selected for eligibility to be president. The only way that this could occur would be for all three positions to be unavailable. For example, these three might be in a single meeting and all killed at once.
Scenario
The presumption here is that every other position in the line of succession would not be qualified (or also dead).
Solution
The obvious solution would be to declare a different Speaker of the House or President pro tempore of the Senate. These positions are controlled by the House and Senate respectively. They require no presidential input nor input from the other chamber. So long as either chamber has a quorum, it could appoint someone by a simple majority vote (which may change any current rules with other requirements).
Now, what would happen if there was no quorum? For example, if Washington, D.C. had been hit by a nuclear bomb, it might easily have wiped out the entire line of succession and both chambers of Congress (possibly leaving someone like Elaine Chao who is ineligible to become president).
In a case where Congress was not available, states have the ability to appoint Senators temporarily. So enough state governments would have to appoint replacement Senators to allow for a quorum in the Senate, which could then appoint a President pro tempore of the Senate. That person would then become acting president. As acting president, that person could nominate a vice president. Congress could approve the nomination (possibly after a bunch of special elections to fill the House). The vice president would be ahead of the President pro tempore of the Senate in the line of succession and would become president.
It would likely be easier to appoint acting Senators than to elect House members. So I am assuming that the Senate would reach a quorum first and select someone to be acting president.
This process assumes that the Speaker of the House would decline to replace the President pro tempore of the Senate as acting president. Because otherwise the Speaker of the House would be higher in the line of succession. The House could instead choose someone specifically to become acting president and replace the President pro tempore of the Senate. But they might not do that, as there may not be anyone who wants to give up a position in the House to become acting president.
Either the acting president (while serving) or the new president (once the oath of office is taken) could refill the line of succession by appointing a new cabinet.