Hook into the loop via a plugin, and output something after every X post?

You can try the following:

Method 1:

We can inject the ads via the the_post action, in the main loop:

add_action( 'loop_start', 'wpse_141253_loop_start' );

function wpse_141253_loop_start( $query )
{
    if( $query->is_main_query() )
    {
        add_action( 'the_post', 'wpse_141253_the_post' );
        add_action( 'loop_end', 'wpse_141253_loop_end' );
    }
}

function wpse_141253_the_post()
{
    static $nr = 0;

    if( 0 === ++$nr % 4 )
        echo '<div> -------- MY AD HERE ------- </div>';
}

function wpse_141253_loop_end()
{
    remove_action( 'the_post', 'wpse_141253_the_post' );   
}    

Method 2:

We can also inject the ads via the the_content filter, in the main loop:

add_action( 'loop_start', 'wpse_141253_loop_start' );

function wpse_141253_loop_start( $query )
{
    if( $query->is_main_query() )
    {
        add_filter( 'the_content', 'wpse_141253_the_content' );
        add_action( 'loop_end', 'wpse_141253_loop_end' );
    }
}

function wpse_141253_the_content( $content )
{
    static $nr = 0;

    if( 0 === ++$nr % 4 )
        $content .= '<div>------- MY AD HERE -------</div>';

    return $content;
}

function wpse_141253_loop_end()
{
    remove_action( 'the_post', 'wpse_141253_the_content' );   
}    

Hopefully you can modify this to your needs.