Ma allora hai praticamente risolto.
Tu hai una matrice nxn, quindi ad ogni squadra possiamo assegnare un indice da 0 ad n-1;
con la funzione Math.random()*( n - 1 ) assegno ad un int un valore che va da 0 ad n-1.
Faccio questa operazione 2 volte ed ho i 2 indici della matrice.
Ho prelevato una partita.
I due indici diventano le mie due squadre da non più toccare.
Nuovamente calcolo due indici, ma questa volta con un indice diverso da quelli estratti in precedenza ( come detto prima potrebbero esser salvati da qualche parte, come un vettore ).

Altrimenti hai 2 vettori con ( 0 ) - ( n-1 ). Generi due numeri, diventano riga e colonna, controlli che gli indici siano presenti nei tuoi vettori e se si prelevi la tua partita. Prelevata la partita rimuovi i due indici dai due vettori ( non so perchè, ma questa soluzione non mi piace ).

Quello a cui devi stare attento è che nella generazione casuale, finchè sei all'inizio ci metti un attimo a generare indici validi, mentre verso la fine, ora che azzecchi l'ultimo o gli ultimi rimasti ci vuole un pò, quindi gestisci bene anche questo.