How to overwrite orderby with add_query_var

Use pre_get_posts instead..

function my_archive_query_override( $query ) {
    if ( $query->is_archive() && $query->is_main_query() ) {
        $query->set( 'orderby', 'rand' );
    }
}
add_action( 'pre_get_posts', 'my_archive_query_override' );

For that user selectable part, you can use AJAX to accomplish that.