If you consider the basics of the Helix principles that features should not be aware of the project layer, you could decide that the "Header" feature you are developing should have 2 sets of contoller-model-view. In my opinion, a feature can have multiple implementations of something that might seem similar. If in your case the header is so different between site A and site B that you cannot fix it in the project layer (as it seems), you actually have 2 cases. You could even decide to create 2 features for it, but that would seem real overkill. So I would create one feature and have 2 possible header implementation in that.
As a comparison, just consider an event feature. You might re-use that event feature over multiple sites. But what if one site want to display the events in a calendar view and the other one just as a flat list? I assume in that case you would also just have a calender view and a list view in your event feature. Just as you would do if those views were wanted in 1 site. The feature doesn't care where you use it. For events this might seem obvious, so I don't see why that would be different for a header.
To resume: I would create 1 feature with 2 options for your header.
