Run “the loop” in a random order

As I understood, you want the same results but randomize their order. So, you need to shuffle that results. That is quite simple using shuflle() PHP function. But that function needs arrays, not objects.

You could convert the object from WP_Query to an array or, I think better, use get_posts() instead of WP_Query.

$args = array(
    // Arguments to get posts
);

$posts = get_transient ( "your-transiente-name" );

if( $posts === false ) {
    $posts =  get_posts( $args );
    set_transient( "your-transiente-name", $posts, "the-expiration-time" );
}

// Shuffle the $post array
$posts = shuffle( $posts );

foreach( $posts as $post ) {
    setup_postdata( $post );
    // Standard loop stuff
}

wp_reset_postdata();