So shutil should be fixed to pass a bytes value to os.listdir().  But
then os.remove() should be fixed to accept bytes as well.  This is the
crux I believe: on Unix at least, syscall wrappers should accept bytes
for filenames.  And this would then have to be extended to things like
the functions in os.path, and we'd need bytes versions of os.sep and
os.altsep...  This sounds like a good project for 3.1.

I do not accept an os.listdir() that raises an error because one
filename cannot be decoded.  It sounds like using errors='replace' is
also wrong -- so the only solution is for os.listdir() to skip files it
cannot decode.  While this doesn't help for rmtree(), it is better than
errors='replace' for code that descends into the tree looking for files
matching a pattern or other property.  So I propose this as a patch for 3.0.

The callback variant is too complex; you could write it yourself by
using os.listdir() with a bytes argument.  This also applies to
proposals like passing optional encoding and errors arguments to
os.listdir().