How to create a front end user profile with a friendly permalink and a 404 trigger

I believe the solution here would be as simple as you’ve generally described it.
Assuming conveniently that $wp_query->query_vars['user'] contains the username and not its ID:

if ( array_key_exists( 'user', $wp_query->query_vars ) ) {
    if ( username_exists( $wp_query->query_vars['user'] ) ) {
        include( TEMPLATEPATH . '/user-profile.php' );
    } else {
        include( TEMPLATEPATH . '/404.php' );
    }
    exit;
}