Not sure because I've never tried test data generation on my own. So this is only a rough guess.
It MAY be that this task cannot be performed out of the box.
If that's the case, then I would suggest splitting up this task in separate steps. Here is one example (not necessarily the best possible approach, just the fastest one to describe).
In step 1, create the country codes.
In step 2, you have to create different "province" codes based on the country. Probably you will need more than one process to perform this task in TDM.
In step 3, based on the country / province combination, you can finally create the cities depending on the results of step 2. Again it might be that you have to set up several distinct generation steps here.
Again, just a rough idea, I've never worked with this particular stuff so far.