We could try to make a road of our own if we could figure out a direction to go... Or maybe there is a road, and it's being hidden from us somehow.

Or you can take a ship to other regions. I mean, neither Kanto nor Johto are landlocked. They just might not be selling us passes to other regions for some reason. Possibly legal. Goodness knows the law system around here confounds me sometimes.