Python:Is there any way to remove an item from a list (random) after it has been used? Or change results of random.choice

I really didn't know how to ask this question, and I probably sound stupid. I've been looking around for solutions to the problem I have been having, but everything I've tried hasn't worked. I'm working on a project for my computer science class, as my final, that randomly generates an identity from a list of names, birthdays, cities, addresses, etc. (sidenote: my teacher hasn't actually taught me anything; we read notes and did quizzes that consisted of definitions from the notes, and when we can't figure something out he just tells us to ask our neighbor. And, this is my first post on here, so if the formatting is incorrect, and my coding skills suck, I apologize in advance.) Anyway, I'll get on with my question/problem.

At the beginning of the program, it asks if you would like to generate a male or female identity:

def get_info():

global gender
global name
gender=input("Enter a gender of which you would like to randomly generate M=male F=female:")  
if gender==("F"):
    name=fname
elif gender==("M"):
    name=mname
else:
    print("Please enter either an M or F.")
    get_info()

which it then uses to determine which list the name comes from:

fname=random.choice(list(set(["girlynames","tina","caroline","etc"])))

or

mname=random.choice(list(set(["guynames","richard","earl","etc"])))

and then it prints out a random identity, including name, birthday, etc. like this:

Your new identity is: 
Nathaniel Ellis
Your birthday is :
September 5 1985
Your address is :
470 MacMurray Acres

and I have added a function, after the main part of the program, that asks for user input if they would like to use the program again.

def retry():

again=input("Would you like to generate another? Y/yes N/no: ")
if again==('Y'):
    get_info()
    generate_identity()
    retry()

elif again==('N'):
    print("Thanks for using the identity generator! Have a spectacular day")
    quit()

The problem is, every time I input 'Y', and a gender, it has the exact same results as it did the first time, even with a different gender all the results are the same besides the first name.

Your new identity is: 
Ava Ellis
Your birthday is :
September 5 1985
Your address is :
470 MacMurray Acres

I feel like there is a simple solution to this, but everything I've read and tried from this website (along with other sources) haven't worked. Is there a way to remove an item from a list after it has been used? Or make it so the results vary every time? Or even a way to just, like, reset Python, since it is only pseudorandom? I have been stumped on this for 3 days now, it is due by next monday, and I've been here on stackoverflow trying to find a solution since I noticed the problem. Help will be greatly appreciated and you'll be a life saver! :)