Take a look at the AppBarButtonStyle defined in StandardStyles.xaml to see how it is done there. It's essentially what you describe with stacked TextBlocks, along with extra styling code to modify the button for different view states.
You can also use the AppBarButtonStyle for your own buttons without having to use the specifically designed ones.
<Button Style="{StaticResource AppBarButtonStyle}"
AutomationProperties.AutomationId="ClickButton"
AutomationProperties.Name="Click"
Click="Button_Click"></Button>
--Rob