A standard example of something that cannot be done without the axiom of choice is choosing one sock from each pair of socks in an infinite collection of pairs of socks. In contrast, it is possible to do a similar thing for shoes with the axiom of replacement, using the functional relation $P(x,y)$ which evaluates to true iff x is a pair of shoes and y is the left shoe from this pair.
Is it possible to construct, in ZF, a collection of pairs whose elements are as indistinguishable as the elements of a pair of socks, so that the axiom of replacement won't help us choose one from each pair? I'm not sure how this would be done without the elements of the pairs actually being equal, which would make them no longer pairs. Any difference between the elements of a pair seems like it would be possible grounds for a functional relation that could circumvent the axiom of choice.