Or will it be best to create each and every document from scratch every time?

For one, it depends on the complexity of the document.  With simple/short documents it's probably "best" to create them from scratch every time — in case you want to operate at the PDF level yourself (like you would when using PDF::API2), and not use some higher level layout package like latex.

As for working with PDF templates, you should be aware that PDF is not a language for laying out documents, but rather a language for low-level description/rendering of drawing instructions, like "print those glyphs or lines at position x,y".  In other words, it doesn't do automatic paragraph layout, text block wrapping, page breaks, etc.

Also, the format doesn't lend itself particularly well to being templated directly, as it typically contains compressed content streams (which you could only modify in uncompressed form), and because the PDF file holds an index table specifying the byte offset of every "object" in the file (not the document index you see in a PDF viewer, but an internal one). When you modify one object in size, all offsets of the objects that follow in the document will have to be adjusted accordingly.

In case you really want to do templating directly at the PDF level, I'd suggest you use pdftk in combination with a template in uncompressed form.  In this case, you could essentially use any text templating module (though it would of course require a reasonable understanding of how PDF works), and pdftk would then handle compressing the document and recomputing the internal object offsets.  I wouldn't recommend this approach, however, unless you are (or want to become) familiar with the guts of PDF, and are making only minor changes, like filling in a few names or addresses, etc.