Você estava certo em considerar renomear primeiro. A sintaxe é um pouco estranha se você não estiver acostumado a regexes, mas é de longe a rota mais rápida / mais curta quando você sabe o que está fazendo:
rename 's/\d{4}/2503/' file*
Isso simplesmente combina os primeiros 4 números e os troca para os que você especificou.
E um equipamento de teste ( -vn
significa ser detalhado, mas não faz nada) usando seus nomes de arquivos:
$ rename 's/\d{4}/2503/' file* -vn
file0901201437404.p renamed as file2503201437404.p
file0901201438761.p renamed as file2503201438761.p
file1003201410069.p renamed as file2503201410069.p
file2602201409853.p renamed as file2503201409853.p
file2602201410180.p renamed as file2503201410180.p