If you search for python yaml unicode, the very first result is this bug report, which has exactly the solution you're looking for. In short, register a custom representer for unicode strings, like this:
yaml.add_representer(unicode,
lambda dumper, value: dumper.represent_scalar(u'tag:yaml.org,2002:str', value))
With this in place, your example renders like this:
>>> d = {3: u'blah', u'b': u'foo', (12,2,3) : u'bonjour'}
>>> print yaml.dump(d)
3: blah
? !!python/tuple [12, 2, 3]
: bonjour
b: foo