I would use the hook tiny_mce_before_init :
function wpse_106063_tinymce($arr){
$arr['theme_advanced_blockformats'] = 'h1,h2,h3,h4';
$style_formats = array(
array('title' => 'title', 'block' => 'h1')),
// etc
);
$arr['style_formats'] = json_encode( $style_formats );
return $arr;
}
add_filter('tiny_mce_before_init', 'wpse_106063_tinymce');
Hope it helps.
EDIT: add something that should work, not tested.
source