What happens when you are hemmed in?
You can just "jump over" other cities. From the rulebook, p. 5 (emphasis mine).


  A player may add any city (if there is room in the city for the
  player) to his network, regardless of its distance from his other
  cities. The player may build through a city without placing a house
  there if he wants or (more likely) if there is no room in the city.


edit: naturally you have to pay any incurring connection costs to the city you are going to. The game does not retain memory of the connection costs that you've paid, so you might have to pay some connection costs twice.

example: consider cities A -- B -- C, with the connection costs being $3 for A -- B and $4 for B -- C. Alice is in city A, Bob in city B, nobody in city C. 


Alice may built in city C! She has to pay $10 for being the first to connect there, plus $7 for the incurring connection costs (A to B, B to C), for a total of $17.
When step 2 kicks in, Alice wants to connect to B. She will pay again the connection costs of $3 between A -- B (because it's cheaper than paying $4 for C -- B) plus $15 for being the second to connect there, for a total of $18. Even though she had paid earlier the connection costs for A -- B, the game does not remember it, so she pays again for it.


NB: originally commented by @GendoIkari, added here with an example for completeness.