почему бы просто не поместить combobox на frame с нужным заголовком? 

Так как вы описали тоже быть не должно.
Если я пользуюсь программой выбираю пункты, а в итоге так и останется "Выбор региона", я решу, что ничего не выбралось. В идеале (на мой взгляд) отображаемое значение QComboBox-a должно стать «Москва, Санкт-Петербург, Новосибирск».
Реализацию не подскажу, извините.

Делайте обычной кнопкой, по нажатии на которую показывайте вьюху дерева popup-окном.

_OLEGator_ и Kolobok большущее спасибо. Оба варианта верные.
Вот как я сделал. Переопределил paintEvent в QComboBox-е.

// Переопределение стандартного метода (перерисовка элемента)
void paintEvent(QPaintEvent *a_pPaintEvent)
{
   QStylePainter StylePainter(this);
   QStyleOptionComboBox StyleOptionComboBox;
   initStyleOption(&StyleOptionComboBox);
   StylePainter.drawComplexControl(QStyle::CC_ComboBox, StyleOptionComboBox);
   StyleOptionComboBox.currentText = "Выбор регионов";
   StylePainter.drawControl(QStyle::CE_ComboBoxLabel, StyleOptionComboBox);
}