Is there a WordPress plugin that registers a plugin file as a custom page template?

Like Rarst answered you can really do that without editing core files or remove the page attributes metabox and create your on using the same code with a bit of modification.
the code below is the code for the /admin/include/meta-boxes.php
and i added the a comment to show where your extra page template options would go:

function page_attributes_meta_box($post) {
    $post_type_object = get_post_type_object($post->post_type);
    if ( $post_type_object->hierarchical ) {
        $pages = wp_dropdown_pages(array('post_type' => $post->post_type, 'exclude_tree' => $post->ID, 'selected' => $post->post_parent, 'name' => 'parent_id', 'show_option_none' => __('(no parent)'), 'sort_column'=> 'menu_order, post_title', 'echo' => 0));
        if ( ! empty($pages) ) {
        ?>
        <p><strong><?php _e('Parent') ?></strong></p>
        <label class="screen-reader-text" for="parent_id"><?php _e('Parent') ?></label>
        <?php echo $pages; ?>
        <?php
        } // end empty pages check
    } // end hierarchical check.
    if ( 'page' == $post->post_type && 0 != count( get_page_templates() ) ) {
        $template = !empty($post->page_template) ? $post->page_template : false;
        ?>
        <p><strong><?php _e('Template') ?></strong></p>
        <label class="screen-reader-text" for="page_template"><?php _e('Page Template') ?></label><select name="page_template" id="page_template">
        <option value="default"><?php _e('Default Template'); ?></option>
        <?php page_template_dropdown($template); ?>

        // add your page templates as options

        </select>
        <?php
    } ?>
    <p><strong><?php _e('Order') ?></strong></p>
    <p><label class="screen-reader-text" for="menu_order"><?php _e('Order') ?></label><input name="menu_order" type="text" size="4" id="menu_order" value="<?php echo esc_attr($post->menu_order) ?>" /></p>
    <p><?php if ( 'page' == $post->post_type ) _e( 'Need help? Use the Help tab in the upper right of your screen.' ); ?></p>
    <?php
}

Don’t know if this is a fix in your case but i had a smiler case when i needed to display the post type in a plugin built-in theme and for that i used add_filter('the_content', 'my-function');
and my-function created the output to display.

Another option would be to make your plugin create the template file in the current theme directory , something like this:

function create_plugins_theme_file(){
    $file_name = TEMPLATEPATH . "https://wordpress.stackexchange.com/" . $tamplate_name . '.php';
    $handle = fopen($file_name, 'w') or wp_die('Cannot open file for editing');
    $file_contents = <<<OUT
<?php
/*
Template Name: $tamplate_name
*/
?>

//you theme file here

OUT;

   fwrite($handle, $file_contents);
   fclose($handle);
 }

and you can run this after you first check if the file exist

if(!file_exists( $file_name)){create_plugins_theme_file();}

Hope one of this helps.