How to control output of custom post type without modifying theme?

There’re two very often forgotten action ref arrays: loop_start/_end().

Just turn on output buffering and you’re ready to go.

add_action( 'loop_start', 'wpse75307_plugin_loop' );
add_action( 'loop_end', 'wpse75307_plugin_loop' );
/**
 * Callback function triggered during:
 * + 'loop_start'/`have_posts()` after the last post gets rendered
 * + 'loop_end'/`the_post()` before the 1st post gets rendered
 * @param  object \WP_Query Passed by reference
 * @return 
 */
function wpse75307_plugin_loop( &$obj )
{
    # if ( is_main_query() )
    # DO STUFF ... OR DONT
    global $post;

    // Start output buffering at the beginning of the loop and abort
    if ( 'loop_start' === current_filter() )
        return ob_start();

    // At the end of the loop, we end the buffering and save into a var
    # if ( is_main_query() )
    # DO STUFF ... OR DONT
    $loop_content = ob_get_flush();

    // You can do something with $loop_content...
    // Add your own loop, or...
    // Whatever you can imagine
}

Note: I wouldn’t do it like this, but as you said, you want exactly that level of overriding, here you go.