Using WP Rewrite to rewrite custom urls in this scenario

In your case would be something like:

add_action('rewrite_rules_array', 'rewrite_rules');
function rewrite_rules($rules) {
    $new_rules = array(
        'product/([0-9]+)/?$' => 'index.php?product=$matches[1]'
    );
    return $rules + $new_rules;
}

add_action('query_vars', 'add_query_vars');
function add_query_vars($vars) {
    array_push($vars, 'product');
    return $vars;
}

add_action('template_redirect', 'custom_template_redirect');
function custom_template_redirect() {
    global $wp_query, $post;
    if (get_query_var('product')) {
        include(YOURPLUGINDIR . 'templates/product_template.php');
        exit();
    }
}

In product_template.php, you can access which product was queried with get_query_var('product').

After modifying the rules array you need to flush the rules. Do this by simply visiting the permalink admin page on http://yoursite/wp-admin/options-permalink.php.

Also, you can see the rules testing order and which one is being matched with:

add_action('wp', 'debug_rules');
function debug_rules() {
    global $wp, $wp_query, $wp_rewrite;
    echo $wp->matched_rule . ' | ' . $wp_rewrite->rules[$wp->matched_rule];
    print_r($wp_rewrite->rules);
    exit();
}

And please, try to make your plugin work for both cases (GET variables and custom rewrite rules), as you never know if your users will be able to run permalinks.

So, as the docs tell us:

if ( get_option('permalink_structure') ) {
    /* do everything as above */
} else {
    /* so stuff only with GET variables
}