Dictionary Parser Class
I would have used str.format together with a transparent dictionary to achieve this result. It gives you the familiarity of the format syntax and not having to come up with the regex on your own. This comes at the cost of not being able to specify the regex anymore at all.

The transparent dict is taken from this answer and is needed because otherwise format raises a KeyError when trying to do a partial replace.

from collections import defaultdict

class SafeDict(dict):
    def __missing__(self, key):
        return '{' + key + '}'


def parse(val, vars, callback=None):
    if callback:
        val = callback(val)
    if isinstance(val, dict):
        return parse_dict(val, vars, callback)
    elif isinstance(val, list):
        return parse_list(val, vars, callback)
    try:
        return val.format(**SafeDict(vars))
    except Exception:
        return val


def parse_list(l, vars, callback=None):
    parsed = type(l)()
    for val in l:
        parsed.append(parse(val, vars, callback))
    return parsed


def parse_dict(d, vars, callback=None):
    parsed = type(d)()
    for key, val in d.items():
        parsed[key] = parse(val, vars, callback)
    return parsed


parse_dict and parse_list could be replaced by the one-liners you use. This way, however, they return the same data type as was originally there (this is relevant for sub-classes of list or dict). If you don't need this, just replace them with what you've got.

usage:

a = 'blah' 
my_dict = {'test': '{a}', 
           'another': 'my {a} test',
           'nested': {'child': 'here is {a} {a}'},
           'boo': 1,
           'test2': False}
print(parse(my_dict, globals()))


When adding more parsers for other data types than list or dict (their sub-classes are already included), you would probably define a mapping from type to parsers to avoid repetition in parse.

As an alternative you should have a look at f-strings, which will be included in Python 3.6, scheduled to be released soon.

With this you could do:

a = 'blah' 
table = "Users"
row = 42
parsed_dict = {'test': f'{a}', 
               'another': f'my {a} test',
               'nested': {'child': f'here is {a} {a}'},
               'boo': 1,
               'test2': False,
               'complex': f'result: {db_lookup(table, row))}'}