I've been doing much the same with my son, who's now 13. From when he was three or so, we'd play 'if you were lost, what would you do' games in stores and shopping streets (in a shop, ask somebody at the till for help; in the street, go into a store); and I had him learn my mobile phone number; and we'd happily leave him to read books and magazines while we did our shopping. He timed out a few times and asked a shop assistant to call us on the intercom and we'd reassure him he'd done the right thing. The aim was to get him thinking 'oh bother, I'm lost /again/'.
When he was eight he moved to Denmark with his mum and they'd get a train each day - but his school was at an earlier stop than her office so he'd get off and walk the last half-mile or so on his own. A few weeks after he arrived there (and speaking no Danish), he got an earlier train back and she wasn't on it. So he got off at the right stop, went to a tourist bureau where he'd been before, and had them phone me in England on my mobile number. He was eight, and on his own in a foreign city - but not, technically, lost. Since then I've not really been too bothered about his finding his way about.
He's now back in England and quite happy to take trains and buses on his own which, of course, is how it should be.