Mutually Exclusive Variable Definitions in Nested Randomisations - Python

I'm attempting to return an output containing several nested random choices of strings from lists using Python's random module with the outputs of variables from choice 1 being exclusive to choice 2. Essentially, I want x_choice1 to never equal x_choice2 in the final output and same goes for y_choice1 and y_choice2. Here's some context... (this is all within a main function, btw).

        x = ["x1", "x2", "x3", "x4"]

        y = ["y1", "y2", "y3", "y4"]

        # Makes random assignment to multiple x choice and y choice variables from x and y lists

        x_choice1 = random.choice(x)
        y_choice1 = random.choice(y)

        x_choice2 = random.choice(x)
        y_choice2 = random.choice(y)

        # z1 and z2 vars combine choices from both lists

        z1 = x_choice1 + " " + y_choice1

        z2 = x_choice2 + " " + y_choice2

        # While loops to make each x and y choice vars mutually 
        # exclusive with additional prints to signal when the program 
        # is re-rolling the value of vars

        while x_choice1 == x_choice2:
            print("reassigning x variables")
            x_choice1 = random.choice(x)
            x_choice2 = random.choice(x)

        while y_choice1 == y_choice2:
            print("reassigning y variables")
            y_choice1 = random.choice(y)
            y_choice2 = random.choice(y)

        # Final variables to combine nested random vars

        final1 = ["first: " + z1, "first: " + z1, "first: " + z1]

        final2 = ["second: " + z2, "second: " + z2, "second: " + z2]

        # Final random selection of nested random vars

        final_choice1 = str(random.choice(final1))

        final_choice2 = str(random.choice(final2))

        # Output both final choices

        output = final_choice1 + " " + final_choice2

        print(output)

This works exactly how I want it to when I remove the 'nesting' of the variables (assigning z1 and z2, the random selection of final1 and final2, etc.). For example...

    x = ["x1", "x2", "x3", "x4"]

    y = ["y1", "y2", "y3", "y4"]

    x_choice1 = random.choice(x)
    y_choice1 = random.choice(y)

    x_choice2 = random.choice(x)
    y_choice2 = random.choice(y)

    while x_choice1 == x_choice2:
        print("reassigning x variables")
        x_choice1 = random.choice(x)
        x_choice2 = random.choice(x)

    while y_choice1 == y_choice2:
        print("reassigning y variables")
        y_choice1 = random.choice(y)
        y_choice2 = random.choice(y)

    output1 = x_choice1 + " " + y_choice1
    output2 = x_choice2 + " " + y_choice2

    print(output1)
    print(output2)

This outputs something like this:

reassigning x variables
reassigning x variables
x3 y1
x2 y4

Which every time never has the first x equivalent to the second and same for y and also triggers the message if it has to re-roll the choices, so I know it works.

How can I make the while loops in the first example work in the same way? At the moment it does trigger the "reassigning variables" message but then the values always return the same (ex. x4 x4, y2 y2).