My own best answer so far involves setting the tableHeaderView once and forcing a layout pass. This allows a required size to be measured, which I then use to set the frame of the header. And, as is common with tableHeaderViews, I have to again set it a second time to apply the change.

- (void)viewDidLoad
{
    [super viewDidLoad];

    self.header = [[SCAMessageView alloc] init];
    self.header.titleLabel.text = @"Warning";
    self.header.subtitleLabel.text = @"This is a message with enough text to span multiple lines. This text is set at runtime and might be short or long.";

    //set the tableHeaderView so that the required height can be determined
    self.tableView.tableHeaderView = self.header;
    [self.header setNeedsLayout];
    [self.header layoutIfNeeded];
    CGFloat height = [self.header systemLayoutSizeFittingSize:UILayoutFittingCompressedSize].height;

    //update the header's frame and set it again
    CGRect headerFrame = self.header.frame;
    headerFrame.size.height = height;
    self.header.frame = headerFrame;
    self.tableView.tableHeaderView = self.header;
}

For multiline labels, this also relies on the custom view (the message view in this case) setting the preferredMaxLayoutWidth of each:

- (void)layoutSubviews
{
    [super layoutSubviews];

    self.titleLabel.preferredMaxLayoutWidth = CGRectGetWidth(self.titleLabel.frame);
    self.subtitleLabel.preferredMaxLayoutWidth = CGRectGetWidth(self.subtitleLabel.frame);
}

Update January 2015

Unfortunately this still seems necessary. Here is a swift version of the layout process:

tableView.tableHeaderView = header
header.setNeedsLayout()
header.layoutIfNeeded()
let height = header.systemLayoutSizeFittingSize(UILayoutFittingCompressedSize).height
var frame = header.frame
frame.size.height = height
header.frame = frame
tableView.tableHeaderView = header

I’ve found it useful to move this into an extension on UITableView:

extension UITableView {
    //set the tableHeaderView so that the required height can be determined, update the header's frame and set it again
    func setAndLayoutTableHeaderView(header: UIView) {
        self.tableHeaderView = header
        header.setNeedsLayout()
        header.layoutIfNeeded()
        let height = header.systemLayoutSizeFittingSize(UILayoutFittingCompressedSize).height
        var frame = header.frame
        frame.size.height = height
        header.frame = frame
        self.tableHeaderView = header
    }
}

Usage:

let header = SCAMessageView()
header.titleLabel.text = "Warning"
header.subtitleLabel.text = "Warning message here."
tableView.setAndLayoutTableHeaderView(header)