Right now, if you can't pass through another factions territory within 1 turn, you are asked to leave.
The logic behind this, of course, is to prevent the human player from declaring war when at AI's doorstep.
However, there is already a amechanic in the game that requires that you be outside of the AI's territory before declaring war, so the request to leave the territory is unecessary.
In my current game, I'm boxed in and can't expand because I'm surrounded by AI factions that I can't pass through in one turn. I'm in the middle of the pack strength wise, but that will rapidly change if I can't expand. I'm not currently strong enough to attack the two AI's boxing me in. (and without the ability to expand I will never be strong enough). The game is effectively over.
My suggestion to minimize the box-in. (but not eliminate it):
If your relations with an AI are neutral or better, AND if you have trade and/or economic treaty with a faction, they should allow you to pass through their territory.
I thought of suggesting a "safe passage treaty" integrated into the diplomacy screen, but the way the diplomacy mechanics work currently, the AI would probably want a small fortune for it....making it a useless option.