You are correct in that VF Email Templates can not use letterheads (this is a feature of HTML email templates)
But you can create a custom VF component and add a reference to it at the end of every VF Email template:
VF Email template:
<messaging:emailTemplate recipientType="Contact"
relatedToType="Account"
subject="Case report for Account: {!relatedTo.name}"
language="{!recipient.language__c}"
replyTo="support@acme.com">
<messaging:htmlEmailBody>
<html>
<body>
<p>Dear {!recipient.name},</p>
... other markup
<c:MyFooter> <!-- THE FOOTER COMPONENT -->
</body>
</html>
</messaging:htmlEmailBody>
</messaging:emailTemplate>
The Custom Component MyFooter
<apex:component>
<h3>Please visit us at www.acme.com</h3> <!-- your markup -->
</apex:component>
These custom components can be as sophisticated as you want - they can include images that link to social media sites, be of different type faces or sizes etc. You can even pass contextual parameters from the parent email template in case some footers need variation.
VisualForce Custom Components reference
ADVISORY: VF Email Templates have rendering issues if the running user is Automated Process (such as in Platform Events). This may have been fixed by the time you are reading this. YMMV
Note: If you have a mix of HTML Letterhead and VF email templates, you will have to duplicate the "work" but at least the VF version is localized, easy to change and footers are unlikely to change often
c:MyFooter
and add to every VF email template? Yes, a duplicate of footer used in letterheads but unlikely to change often – cropredy Aug 10 '20 at 18:06