MySQL: Select two values of two columns and compared their values exchanging them each other
I guess, from the description, that you first need all rows with rows (x,y) where no other row (y,x) exists. Then select a random row from them:

SELECT r.leader, r.subscriber 
FROM relations AS r 
WHERE NOT EXISTS
      ( SELECT *
        FROM relations AS r2
        WHERE r.subscriber = r2.leader
          AND r.leader = r2.subscriber     -- or perhaps without this
      ) 
ORDER BY RAND()
LIMIT 1 ;  


It would be useful to have two indexes, on (leader, subscriber) and on (subscriber, leader). If the table is very big and performance is still not good, you may have to change how the random row is selected. The ORDER BY RAND LIMIT 1 solution works ok in small tables but it's quite slow in big tables as it has to sort all the matching rows before it chooses one.