O meu conselho é simplesmente renomear crescentemente, pois colocar a data como sufixo/prefixo (ex: dd-mm-yyy_hh:mm:ss) em um ciclo como este exemplo arriscarias muitos ficheiros com nomes iguais (iriam ser alterados no mesmo segundo ou até milisegundo):
Por comentário percebi que talvez tenhas de correr isto várias vezes, assim é preciso obter o último n
do último ficheiro mudado para renomear o primeiro a seguir como (n+1)_foo.pdf
:
import os
original_dir = 'caminho/para/pasta/original'
files = os.listdir(original_dir) # todos os ficheiros
last_num = max(int(i.split('_', 1)[0]) for i in files if '_' in i) # ultimo numero
no_changed_files = (i for i in files if '_' not in i) # ficheiros ainda nao mudados
for n, file_name in enumerate(no_changed_files, last_num + 1): # renomear os que ainda nao foram
full_path = os.path.join(original_dir, file_name)
if (os.path.isfile(full_path)): # se for ficheiro
os.rename(full_path, '{}/{}_{}'.format(original_dir, n, file_name))