It's a bit easier if you can co-operate with the other programs that might create files there.

Anyway, here's one solution that can work if the other programs don't co-operate (of course, the other programs can be very badly behaved, and overwrite your files by force :), even on NFS.

First, create a new empty directory in the destination directory. We assume that only you will use this directory, and other programs won't create files in it. Then copy the file into that directory with an arbitary name. Than create a symlink in the original directory with the name you are planning to use as the name of the old file eventually. Creating a symlink doesn't overwrite an existing file (not even a symlink), but rather fail in that case. If that happens, choose a new name. Then, rename the copied file from inside the directory to the same name as this symlink. This will overwrite the symlink, but do it atomically: the name will never cease to exist. Finally, remove the directory.

(If you want to copy a directory, this won't work, but that case is simpler anyway, as directory creation won't overwrite anything anyway.)

Update: there are existing functions (not neccessarily perl) that create unique temporary files. Try looking at their sources to see what they do.

Update: it might be simpler to just create a file with the mknod syscall, because that doesn't overwrite an existing file. Then, you don't have to move anything. That works through NFS too (although I didn't test whether it was really atomic), but it might not work on all systems.