The shutil.move function uses os.rename to move files on the same file system. On unix, this function will overwrite an existing destination, so the obvious approach is

if not os.path.exists(dst):
    shutil.move(src, dst)

But this could result in race conditions if dst is created after os.path.exists and before shutil.move.  From my research, it seems that this is a limitation in the unix c library, but it should be possible to avoid it through a workaround (pieced together from http://bytes.com/topic/python/answers/555794-safely-renaming-file-without-overwriting ).  This involves some fairly low-level work, so I propose adding a new move2 function to shutil, which raises an error if dst exists and locking it if it doesn't:

def move2(src, dst):
    try:
        fd = os.open(dst, os.O_EXCL | os.O_CREAT)
    except OSError:
        raise Error('Destination exists')
    try:
        move(src, dst)
    finally:
        os.close(fd)

This could be optimised by using shutil.move code rather than just calling it, but the idea is that an attempt is made to create dst with exclusive access. If this fails, then it means that the file exists, but if it passes, then dst is locked so no other process can create it.

As suggested on the mailing list (http://mail.python.org/pipermail/python-ideas/2011-August/011132.html), an alternative is to add this behaviour as an argument to shutil.move, which may be a neater solution.  

I will work on a patch for this and try to submit it in the next few days.