Instead of using page templates to define layouts, define layouts using custom post meta. The custom post meta can then be shown or not shown using is_plugin_active().
If you’re going to define the page template itself in the Theme, then you’re pretty much stuck with doing something like determining if the Plugin is active (which, on the front end, should be done using a function_exists() conditional or something similar), and including the default template if not. For example:
/**
* Template Name: Shop
*/
if ( ! function_exists( 'some-woocommerce-function' ) ) {
get_template_part( 'page' );
} else {
// Shop template markup goes here
}
That way, even if the template is selected, it will gracefully degrade.