Random but not repeating sampling between two dataframes

I have two dataframes:

DF1:

    UNIQUE_ID   City
k5WjB6MQa5Cru Skopje
k4Yq5QqXwoL4e Skopje
S9jGzT5qMZLyF Skopje
mhSHSuxic58Sf Skopje
MU7eys8NKXQog Skopje
GUBe1scNsXQog Bitola
S9jGzT5qMZLyF Kumanovo

DF2:

  ADDRESS                        City  
 РАТКО МИТРОВИЌ 5 БР.29-ДРАЧЕВО Skopje
 УЛ. МЕТОДИЈА ПАТЧЕВ БР.17А     Skopje
 УЛ ДРАЧЕВСКА 123               Skopje
 УЛ.ДОМАЗЕТОВСКА БР. 24         Skopje
 ДРАЧЕВО УЛ. ЈАНКО МИШИЌ БР. 3  Skopje
 УЛ. ПАРТИЗАНСКИ ПАТ 2 БР. 1    Skopje

I want to assign a random address for each unique ID in DF1. The assignment should fulfill two criteria:

1. The address should not repeat until all unique addresses from DF2 are used up;
2. The address should be pulled for the respective city.

So the desired output would look like:

New_DF

    UNIQUE_ID   City   ADRESS
k5WjB6MQa5Cru Skopje   РАТКО МИТРОВИЌ 5 БР.29-ДРАЧЕВО
k4Yq5QqXwoL4e Skopje   УЛ. МЕТОДИЈА ПАТЧЕВ БР.17А
S9jGzT5qMZLyF Skopje   УЛ ДРАЧЕВСКА 123
mhSHSuxic58Sf Skopje   УЛ.ДОМАЗЕТОВСКА БР. 24
MU7eys8NKXQog Skopje   ДРАЧЕВО УЛ. ЈАНКО МИШИЌ БР. 3
GUBe1scNsXQog Bitola   NA
S9jGzT5qMZLyF Kumanovo NA

Any ideas?