Could use MapThread.
MapThread
MapThread[ RandomSample[Rule[##], 1] &, {{{0.5, 0.5}, {0.4, 0.6}}, {{2, 4}, {3, 5}}}]
Probably
RandomSample[{0.5, 0.5} -> {2, 4}, 1]~Join~RandomSample[{0.4, 0.6} -> {3, 5}, 1]