I found a problem other than the read-only file using shutil.rmtree on Windows (testing on Windows 7).  I was using a combination of shutil.rmtree and shutil.copytree to create a test fixture in a test suite, so the sequence was being called repeatedly in a short period of tme (<1 sec intervals), and I was seeing unpredictable failures part way through the test suite, with both EACCES and ENOTEMPTY errors reported.  The symptoms suggested to me that the shutil.rmtree function had not completed on return to the calling program, and that it was only after some time that the deleted filenames were available for re-use.
TL;DR:  the solution isn't pretty - broadly, it renames the directory before deleting it, but there are a number of wrinkles that need to be handled because the Windows file system seems to take some time to catch up with the operations perfumed.  The actual code catches a variety of failure conditions and retries a variant of the failed operation after a short delay.
A longer discussion follows, with my final code at the end.
My first thought was to try renaming the directory tree before removing it, so that the original directory name is immediately available for re-use.  This does appear to help.  To this end, I created a replacement for rmtree whose essence is this:
def removetree(tgt):
    def error_handler(func, path, execinfo):
        e = execinfo[1]
        if e.errno == errno.ENOENT or not os.path.exists(path):
            return              # path does not exist - treat as success
        if func in (os.rmdir, os.remove) and e.errno == errno.EACCES:
            os.chmod(path, stat.S_IRWXU| stat.S_IRWXG| stat.S_IRWXO) # 0777
            func(path)          # read-only file; make writable and retry
        raise e
    tmp = os.path.join(os.path.dirname(tgt),"_removetree_tmp")
    os.rename(tgt, tmp)
    shutil.rmtree(tmp, onerror=error_handler)
    return
I found this logic was an improvement, but it was subject to unpredictable failure of the os.rename operation, with one of several possible errors.  So I also added some retry logic around os.rename, thus:
def removetree(tgt):
    def error_handler(func, path, execinfo):
        # figure out recovery based on error...
        e = execinfo[1]
        if e.errno == errno.ENOENT or not os.path.exists(path):
            return              # path does not exist
        if func in (os.rmdir, os.remove) and e.errno == errno.EACCES:
            os.chmod(path, stat.S_IRWXU| stat.S_IRWXG| stat.S_IRWXO) # 0777
            func(path)          # read-only file; make writable and retry
        raise e
    # Rename target directory to temporary value, then remove it
    count = 0 
    while count < 10:           # prevents indefinite loop
        count += 1
        tmp = os.path.join(os.path.dirname(tgt),"_removetree_tmp_%d"%(count))
        try:
            os.rename(tgt, tmp)
            shutil.rmtree(tmp, onerror=error_handler)
            break
        except OSError as e:
            time.sleep(1)       # Give file system some time to catch up
            if e.errno in [errno.EACCES, errno.ENOTEMPTY]:
                continue        # Try another temp name
            if e.errno == errno.EEXIST:
                shutil.rmtree(tmp, ignore_errors=True)  # Try to clean up old files
                continue        # Try another temp name
            if e.errno == errno.ENOENT:
                break           # 'src' does not exist(?)
            raise               # Other error - propagate
    return
The above code is not tested, but the general idea here does seem to work.  The full code I actually use is below, and uses two functions.  It probably contains some unnecessary logic, but does seem to be working more reliably for me (in that my test suite now passes repeatedly on Windows where previously it failed unpredictably on a majority of runs):
def renametree_temp(src):
    """
    Rename tree to temporary name, and return that name, or 
    None if the source directory does not exist.
    """
    count = 0 
    while count < 10:      # prevents indefinite loop
        count += 1
        tmp = os.path.join(os.path.dirname(src),"_removetree_tmp_%d"%(count))
        try:
            os.rename(src, tmp)
            return tmp      # Success!
        except OSError as e:
            time.sleep(1)
            if e.errno == errno.EACCES:
                log.warning("util.renametree_temp: %s EACCES, retrying"%tmp)
                continue    # Try another temp name
            if e.errno == errno.ENOTEMPTY:
                log.warning("util.renametree_temp: %s ENOTEMPTY, retrying"%tmp)
                continue    # Try another temp name
            if e.errno == errno.EEXIST:
                log.warning("util.renametree_temp: %s EEXIST, retrying"%tmp)
                shutil.rmtree(tmp, ignore_errors=True)  # Try to clean up old files
                continue    # Try another temp name
            if e.errno == errno.ENOENT:
                log.warning("util.renametree_temp: %s ENOENT, skipping"%tmp)
                break       # 'src' does not exist(?)
            raise           # Other error: propagaee
    return None
def removetree(tgt):
    """
    Work-around for python problem with shutils tree remove functions on Windows.
    See:
        https://stackoverflow.com/questions/23924223/
        https://stackoverflow.com/questions/1213706/
        https://stackoverflow.com/questions/1889597/
        http://bugs.python.org/issue19643
    """
    # shutil.rmtree error handler that attempts recovery from attempts 
    # on Windows to remove a read-only file or directory (see links above).
    def error_handler(func, path, execinfo):
        e = execinfo[1]
        if e.errno == errno.ENOENT or not os.path.exists(path):
            return          # path does not exist: nothing to do
        if func in (os.rmdir, os.remove) and e.errno == errno.EACCES:
            try:
                os.chmod(path, stat.S_IRWXU| stat.S_IRWXG| stat.S_IRWXO) # 0777
            except Exception as che:
                log.warning("util.removetree: chmod failed: %s"%che)
            try:
                func(path)
            except Exception as rfe:
                log.warning("util.removetree: 'func' retry failed: %s"%rfe)
                if not os.path.exists(path):
                    return      # Gone, assume all is well
                raise
        if e.errno == errno.ENOTEMPTY:
            log.warning("util.removetree: Not empty: %s, %s"%(path, tgt))
            time.sleep(1)
            removetree(path)    # Retry complete removal
            return
        log.warning("util.removetree: rmtree path: %s, error: %s"%(path, repr(execinfo)))
        raise e
    # Try renaming to a new directory first, so that the tgt is immediately 
    # available for re-use.
    tmp = renametree_temp(tgt)
    if tmp:
        shutil.rmtree(tmp, onerror=error_handler)
    return
(The above code incorporates a solution to the read-only file problem from What user do python scripts run as in windows?, which according to Deleting directory in Python is tested.  I don't think I encounter the read-only file problem, so assume it is not tested in my test suite.)