I wonder if another thought might be to allow all of the lone player's pieces to begin promoted?
An alternate solution might involve allowing the King to teleport up to a given number of squares.
Or, perhaps a further alternate might be if the King were to be able to switch places with another piece of his choice should he be placed in check (but not in mate)?