My understanding is that when a player has to "resolve" Theon, after losing by 4 or more and is forced to choose and discard a character or location, he is able to choose a location, even if the player only has characters on the board. Is this correct?

Yes, that´s correct. A player can choose locations even if he hasn´t any locations in play.