And I mean completely out. Everything is on the board or on player cards, the discard pile is empty. How do you select a random space in this case?

Roll a d6 and subtract one, then multiple that value by six, then roll a second d6 and add that value. If result is more than 21, then count of that many from the left hand side of the map. e.g. San Francisco = 22, Arkham = 23 , Amazon = 24, etc.

This seems like it should be a rare situation so it wouldn't seem too overpowered and for simplicity to select a location.

select a location.

This. Reference guide page 9, "Random Space", first/only bullet point (after the entry's main text).