zip() Isn't needed as the data is already structured. Instead lets use list comprehension.

player_nationalities = [(name, info['nationality']) for name, info in players.items()]
print(player_nationalities)

This will output the required list of tuples.