Регэкспом или даже простым поиском заменой - быстро будет.
Только проверять шаблон чтобы название переменных ни с каким текстом в шаблоне не совпали.
Другой вариант - хранить шаблон в формате какого нибудь шаблонизатора.
Например, Jinja2, Maco, Chameleon и т.п.
И просто скармливать шаблонизатору текст html-шаблона и переменные.
Это будет идеологически правильно, но медленее