I don’t think that there will be a perfect solution to your problem, you already seem to be aware of the pros and cons. If you end up using the same third-party software in all your AppVM, I don’t think that installing this in the template is a big deal. Some redundancy while using Qubes seems mandatory right now.
I also have an AppVM with software installed in the user space, that I clone to keep my configuration. A clever way would be to use salt to manage configuration changes, installed programs, etc. in each VM and in the /etc/skel of the template. But you need to precisely know what configuration file you need to edit. See: