Show different page for first time user

Use template_include with your conditional for first time visitor:

add_filter( 'template_include', 'first_time_visitor_template', 99 );

function first_time_visitor_template( $template ) {

    if ( // your conditional for first time visitor {
        $new_template = locate_template( array( 'first-time-template.php' ) );
        if ( '' != $new_template ) {
            return $new_template ;
        }
    }

    return $template;
}

Do NOT use template_redirect

You will need to test what solution works for a first time visitor.