Wordpress - Create custom page templates with plugins?

get_page_template() can be overridden via the page_template filter. If your plugin is a directory with the templates as files in them, it's just a matter of passing the names of these files. If you want to create them "on the fly" (edit them in the admin area and save them in the database?), you might want to write them to a cache directory and refer to them, or hook into template_redirect and do some crazy eval() stuff.

A simple example for a plugin that "redirects" to a file in the same plugin directory if a certain criterium is true:

add_filter( 'page_template', 'wpa3396_page_template' );
function wpa3396_page_template( $page_template )
{
    if ( is_page( 'my-custom-page-slug' ) ) {
        $page_template = dirname( __FILE__ ) . '/custom-page-template.php';
    }
    return $page_template;
}

Overriding get_page_template() is just a quick hack. It does not allow the template to be selected from the Admin screen and the page slug is hard-coded into the plugin so the user has no way to know where the template is coming from.

The preferred solution would be to follow this tutorial which allows you to register a page template in the back-end from the plug-in. Then it works like any other template.

 /*
 * Initializes the plugin by setting filters and administration functions.
 */
private function __construct() {
        $this->templates = array();

        // Add a filter to the attributes metabox to inject template into the cache.
        add_filter('page_attributes_dropdown_pages_args',
            array( $this, 'register_project_templates' ) 
        );

        // Add a filter to the save post to inject out template into the page cache
        add_filter('wp_insert_post_data', 
            array( $this, 'register_project_templates' ) 
        );

        // Add a filter to the template include to determine if the page has our 
        // template assigned and return it's path
        add_filter('template_include', 
            array( $this, 'view_project_template') 
        );

        // Add your templates to this array.
        $this->templates = array(
                'goodtobebad-template.php'     => 'It\'s Good to Be Bad',
        );
}

Yes, it is possible. I found this example plugin very helpful.

Another approach that is come into my head is using WP Filesystem API to create the template file to theme. I am not sure that it is the best approach to take, but I am sure it work!