How to create Parent-Child relation for custom fields?

This is doable, the meta data itself has no heriarchy, they’re simple key value pairs attached to a Post ID, nothing more. You would be ebtter implementing these yourself via metaboxes, rather than relying on a dedicated generic plugin as you have been doing. It would take you a lot more time and effort to retrofit the plugin you’re using than it would be to simply write your own metabox.

For details on how to create your own metabox and save the details, see this codex page with code examples:

http://codex.wordpress.org/Function_Reference/add_meta_box

Doing this, I would have a dropdown for the country, followed by a set of dropdowns for each province/state hidden and shown by jquery.

Although I would much rather use a single combo box and use grouping instead and store both the country and the state/province/county in the value.

e.g.

<select id="location" name="location">
    <optgroup label="United States">
        <option value="us_virginia">Virginia</option>
        <option value="us_alaska">Alaska</option>
        <option value="us_texas">Texas</option>
        etc...
    </optgroup>
    <optgroup label="United Kingdom">
        <option value="uk_london">London</option>
        <option value="uk_devon">Devon</option>
        <option value="uk_yorkshire">Yorkshire</option>
    etc...
    </optgroup>
</select>