crear campos nuevos en un form mediante php

[quinqui]

Tengo entendido que agregar inputs en tiempo de ejecución se puede hacer con Javascript. Es rápido para el usuario y no le recarga la página, pero personalmente nunca lo he intentado, así que no sé qué tan lento de programar sea.

Si quieres hacerlo con PHP tendrás que ir recargando la página cada vez que quieran agregar un nuevo input.
En ese caso tendrás que estar tomando los valores recibidos por el POST cada vez que se recargue el formulario, y asignándole en el value el valor recibido respectivamente.
Para saber cuántos inputs debe haber por cada recarga, puedes guardar en un campo oculto del formulario un contador de inputs: de modo que si la persona presiona "Agregar Línea", al recargar la página imprima los inputs con sus respectivos valores + 1 vacío. Para todos estos efectos es bueno que guardes los valores de las líneas en un arreglo.