You referred to <c:{!@label.ComponentName} />
as the kind of solution you want. While it probably won't involve Custom Labels, you are definitely close with Dynamic Visualforce.
To do this in a package does require a number of moving parts, but the following is probably the most native-friendly and future-proof approach. And it works! Hope this gets you started:

Inside your managed package, you would have to implement:
VF.page (you might wanna read up on apex:dynamicComponent tag)
<apex:page controller="PageController">
<!-- your header here -->
<apex:dynamicComponent componentValue="{!CustomComponent}" />
<!-- your footer here -->
</apex:page>
PageController.cls (definitely read up on Type.forName)
global class PageController {
public ApexPages.Component getCustomComponent() {
//eg 'AcmeComponentProvider'
ComponentSetting__c setting = ComponentSetting__c.getValues();
//take the string that corresponds to the customer class name
Type reflector = Type.forName(setting.FullyQualifiedClassName__c);
//use the returned Type to instantiate the customer class and cast it
IComponentProvider provider = (IComponentProvider)reflector.newInstance();
//give it to the page
return provider.provideComponent();
}
}
IComponentProvider.cls (making sneaky use of the ApexPages.Component base class)
global interface IComponentProvider {
ApexPages.Component provideComponent();
}
ComponentSetting__c.object

Your customer, in their own organization, would need to implement:
Acme.component
<apex:component >
<!-- special acme specific content -->
</apex:component>
AcmeComponentProvider.cls
public class AcmeComponentProvider implements IComponentProvider {
public ApexPages.Component provideComponent() {
return new Component.Acme();
}
}
Then you need to show them how to Manage the appropriate Custom Setting:
