Se non vuoi usare js, puoi salvare il file al primo passaggio in una posizione temporanea (ti crei una cartella apposta), e se il nome di destinazione esiste già proponi un campo di testo per cambiare nome del file, riproponendo il campo fintanto che viene inserito un nome di file già presente.
Nella terza pagina una volta ricevuto un nome valido sposti il file dalla cartella temporanea alla cartella dell'upload rinominandolo con il nuovo nome.

Solo php senza bisogno di javascript, unico accorgimento, ogni tanto devi svuotare la cartella temporanea, per eliminare residui di upload non terminati.

Ciao.