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.

About new function vs. new argument: this could be asked on python-dev (or on the core-mentorship list if you prefer an environment guaranteed friendly).  If you look at copy and copy2, you’ll see that adding a function was chosen, but the names are not helpful at all.  In more recent shutil development, arguments like copy_function and ignore (on copytree) were added to let people customize behavior without rewriting all the function logic.  Guido van Rossum has a rule about not adding an argument when the value is always a constant, preferring another function instead, but I’m not sure I remember it clearly, so asking for other developers’ thoughts would be good.

A bit of research has shown that the proposed implementation will not work either, so my next suggestion is something along the lines of

def move2(src, dst):
    try:
        os.link(src, dst)
    except OSError as err:
        # handle error appropriately, raise shutil.Error if dst exists,
        # or use shutil.copy2 if dst is on a different filesystem.
        pass
    else:
        os.unlink(src)