(e.g. just replace the template name leaving brakets
and parameters untouched i.e. {{template|1=parameter}}).
This is the easiest case if only the template names change and there are no nested templates. That's what replace.py is for.
A fix r'\{\{oldtemplate(\|.*?)\}\}', r'{{newtemplate\1}}' should do the work.
A less elegant trick, if your problem is, that template.py should be run several times: put the commands in a batch file / bash script.