> More fun will arise when my Windows terminal (encoding=cp1252) 
> will try to display Chinese characters. Let's pretend this is 
> yet another issue.

I tried the patch using a script with unicode characters (character 
not representable in ISO-8859-1 like polish characters ł and Ł).

Result in an UTF-8 terminal (my default locale):
   Traceback (most recent call last):
     File "unicode.py", line 2, in <module>
       raise ValueError("unicode: Łł")
    ValueError: unicode: Łł
=> correct

Result in an ISO-8859-1 terminal (I changed the encoding in my Konsole 
configuration):
   Traceback (most recent call last):
     File "unicode.py", line 2, in <module>
       raise ValueError("unicode: \u0141\u0142")
   ValueError: unicode: \u0141\u0142
=> correct

Why does it work? It's because PyErr_Display() uses sys.stderr instead 
of sys.stdout and sys.stderr uses a different unicode error mechanism:
   >>> import sys
   >>> sys.stdout.errors
   'strict'
   >>> sys.stderr.errors
   'backslashreplace'

Which is a great idea :-)

You can try on Windows using the new attached file unicode.py.