Display all months with posts and inside each month show the 5 latest posts

one possibility is to run all posts through the loop and only output the month once per new month:

<?php       
$counter = 0;
$ref_month="";
$monthly = new WP_Query(array('posts_per_page' => -1));
if( $monthly->have_posts() ) : while( $monthly->have_posts() ) : $monthly->the_post();

    if( get_the_date('mY') != $ref_month ) { 
        if( $ref_month ) echo "\n".'</ul>';
        echo "\n".'<h6>'.get_the_date('F').'</h6>';
        echo "\n".'<ul>';
        $ref_month = get_the_date('mY');
        $counter = 0;
    }

if( $counter++ < 5 ) echo "\n".'   <li><a href="https://wordpress.stackexchange.com/questions/58078/.get_permalink($post->ID).">'.get_the_title($post->ID).'</a></li>';

endwhile; 
echo "\n".'</ul>';
endif; 
?>