As Joel pointed out in the comments, although an answer to this question was accepted there remained the issue of whether the statement in question was equivalent to the axiom of choice. By modifying the proof of Joel's theorem about sets of reals admitting rigid binary relations, I believe I can show that in the standard Cohen model $M$ for the failure of AC the statement "every set admits a rigid binary relation" holds. In particular, this statement is strictly weaker than AC and fails to imply any of the choice principles that fail in that model. A further question that might be interesting is whether every set in this model admits a rigid linear order.

Theorem. In $M$ every set of reals admits a rigid binary relation.

Proof. Throughout we work in $M$. There is a set of reals $A$ such that any set $x$ can be injected into $A^{<\omega}\times\gamma$ for some ordinal $\gamma$ (see for example Lemma 5.25 in Jech's The Axiom of Choice). So any set can be injected into $\mathbb{R}^{<\omega}\times\gamma$ and indeed into $\mathbb{R}\times\gamma$ for some $\gamma$. Thus to prove the theorem it is in fact enough to strengthen Joel's theorem and prove that every subset $X$ of $\mathbb{R}\times\gamma$ admits a rigid binary relation. The proof is really just a slight tweaking, but I'll write it out. Let $ < $ denote the lexicographical ordering on $\mathbb{R}\times\gamma$ inherited from the two usual linear orderings on the component sets. (I identify $\mathbb{R}$ with Cantor space $2^\omega$).

Case 1: $X$ has no countably infinite subset. Then $ < $ restricted to $X$ is rigid, as any nontrivial permutation allows us to iterate the map countably many times on some moved element and get a countable subset.

Case 2: $X$ has a countably infinite subset $z_0,\ldots z_n,\ldots$ (and grab some other point $z^* $). Let $Z=\{z^* ,z_0,\ldots z_n,\ldots\}$. We define a rigid binary relation $R$ as follows. We set $R(z^* ,z^* )$ and put $z_0,\ldots z_n,\ldots$ below $z^* $ in ordertype $\omega$. Let $s_0,\ldots s_n\ldots$ enumerate the finite binary sequences. Then for $\langle x,\alpha\rangle\not\in Z$ we put $R(z_n,\langle x,\alpha\rangle)$ iff $s_n\subseteq x$. For $\langle x,\alpha\rangle$ and $\langle y,\beta\rangle$ both not in $Z$ we let $R(\langle x,\alpha\rangle,\langle y,\beta\rangle)$ hold iff $\langle x,\alpha\rangle<\langle y,\beta\rangle$.

We claim that $R$ is rigid. Let $\pi:X\rightarrow X$ be an $R$-automorphism. As in Joel's proof it is easy to see that every member of $Z$ gets fixed, and that as a result that whenever $\pi(x,\alpha)=(y,\beta)$ we must have $x=y$. It easily follows from this that $\pi$ fixes the second coordinate of every member of $X\setminus Z$ as well, as now $\pi$ restricted to the second coordinate is an automorphism of a subset of $\gamma$, with respect to the usual well-ordered relation on $\gamma$.

As Joel pointed out in the comments, although an answer to this question was accepted there remained the issue of whether the statement in question was equivalent to the axiom of choice. By modifying the proof of Joel's theorem about sets of reals admitting rigid binary relations, I believe I can show that in the standard Cohen model $M$ for the failure of AC the statement "every set admits a rigid binary relation" holds. In particular, this statement is strictly weaker than AC and fails to imply any of the choice principles that fail in that model. A further question that might be interesting is whether every set in this model admits a rigid linear order.

Theorem. In $M$ every set admits a rigid binary relation.

Proof. Throughout we work in $M$. There is a set of reals $A$ such that any set $x$ can be injected into $A^{<\omega}\times\gamma$ for some ordinal $\gamma$ (see for example Lemma 5.25 in Jech's The Axiom of Choice). So any set can be injected into $\mathbb{R}^{<\omega}\times\gamma$ and indeed into $\mathbb{R}\times\gamma$ for some $\gamma$. Thus to prove the theorem it is in fact enough to strengthen Joel's theorem and prove that every subset $X$ of $\mathbb{R}\times\gamma$ admits a rigid binary relation. The proof is really just a slight tweaking, but I'll write it out. Let $ < $ denote the lexicographical ordering on $\mathbb{R}\times\gamma$ inherited from the two usual linear orderings on the component sets. (I identify $\mathbb{R}$ with Cantor space $2^\omega$).

Case 1: $X$ has no countably infinite subset. Then $ < $ restricted to $X$ is rigid, as any nontrivial permutation allows us to iterate the map countably many times on some moved element and get a countable subset.

Case 2: $X$ has a countably infinite subset $z_0,\ldots z_n,\ldots$ (and grab some other point $z^* $). Let $Z=\{z^* ,z_0,\ldots z_n,\ldots\}$. We define a rigid binary relation $R$ as follows. We set $R(z^* ,z^* )$ and put $z_0,\ldots z_n,\ldots$ below $z^* $ in ordertype $\omega$. Let $s_0,\ldots s_n\ldots$ enumerate the finite binary sequences. Then for $\langle x,\alpha\rangle\not\in Z$ we put $R(z_n,\langle x,\alpha\rangle)$ iff $s_n\subseteq x$. For $\langle x,\alpha\rangle$ and $\langle y,\beta\rangle$ both not in $Z$ we let $R(\langle x,\alpha\rangle,\langle y,\beta\rangle)$ hold iff $\langle x,\alpha\rangle<\langle y,\beta\rangle$.

We claim that $R$ is rigid. Let $\pi:X\rightarrow X$ be an $R$-automorphism. As in Joel's proof it is easy to see that every member of $Z$ gets fixed, and that as a result whenever $\pi(x,\alpha)=(y,\beta)$ we must have $x=y$. It easily follows from this that $\pi$ fixes the second coordinate of every member of $X\setminus Z$ as well, as now $\pi$ restricted to the second coordinate is an automorphism of a subset of $\gamma$, with respect to the usual well-ordered relation on $\gamma$.

As Joel pointed out in the comments, although an answer to this question was accepted there remained the issue of whether the statement in question was equivalent to the axiom of choice. By modifying the proof of Joel's theorem about sets of reals admitting rigid binary relations, I believe I can show that in the standard Cohen model $M$ for the failure of AC the statement "every set admits a rigid binary relation" holds. In particular, this statement is strictly weaker than AC and fails to imply any of the choice principles that fail in that model.

Theorem. In $M$ every set of reals admits a rigid binary relation.

Proof. Throughout we work in $M$. There is a set of reals $A$ such that any set $x$ can be injected into $A^{<\omega}\times\gamma$ for some ordinal $\gamma$ (see for example Lemma 5.25 in Jech's The Axiom of Choice). So any set can be injected into $\mathbb{R}^{<\omega}\times\gamma$ and indeed into $\mathbb{R}\times\gamma$ for some $\gamma$. Thus to prove the theorem it is in fact enough to strengthen Joel's theorem and prove that every subset $X$ of $\mathbb{R}\times\gamma$ admits a rigid binary relation. The proof is really just a slight tweaking, but I'll write it out. Let $ < $ denote the lexicographical ordering on $\mathbb{R}\times\gamma$ inherited from the two usual linear orderings on the component sets. (I identify $\mathbb{R}$ with Cantor space $2^\omega$).

Case 1: $X$ has no countably infinite subset. Then $ < $ restricted to $X$ is rigid, as any nontrivial permutation allows us to iterate the map countably many times on some moved element and get a countable subset.

Case 2: $X$ has a countably infinite subset $z_0,\ldots z_n,\ldots$ (and grab some other point $z^* $). Let $Z=\{z^* ,z_0,\ldots z_n,\ldots\}$. We define a rigid binary relation $R$ as follows. We set $R(z^* ,z^* )$ and put $z_0,\ldots z_n,\ldots$ below $z^* $ in ordertype $\omega$. Let $s_0,\ldots s_n\ldots$ enumerate the finite binary sequences. Then for $\langle x,\alpha\rangle\not\in Z$ we put $R(z_n,\langle x,\alpha\rangle)$ iff $s_n\subseteq x$. For $\langle x,\alpha\rangle$ and $\langle y,\beta\rangle$ both not in $Z$ we let $R(\langle x,\alpha\rangle,\langle y,\beta\rangle)$ hold iff $\langle x,\alpha\rangle<\langle y,\beta\rangle$.

We claim that $R$ is rigid. Let $\pi:X\rightarrow X$ be an $R$-automorphism. As in Joel's proof it is easy to see that every member of $Z$ gets fixed, and that as a result that whenever $\pi(x,\alpha)=(y,\beta)$ we must have $x=y$. It easily follows from this that $\pi$ fixes the second coordinate of every member of $X\setminus Z$ as well, as now $\pi$ restricted to the second coordinate is an automorphism of a subset of $\gamma$, with respect to the usual well-ordered relation on $\gamma$. QED.

As Joel pointed out in the comments, although an answer to this question was accepted there remained the issue of whether the statement in question was equivalent to the axiom of choice. By modifying the proof of Joel's theorem about sets of reals admitting rigid binary relations, I believe I can show that in the standard Cohen model $M$ for the failure of AC the statement "every set admits a rigid binary relation" holds. In particular, this statement is strictly weaker than AC and fails to imply any of the choice principles that fail in that model. A further question that might be interesting is whether every set in this model admits a rigid linear order.

Theorem. In $M$ every set of reals admits a rigid binary relation.

Proof. Throughout we work in $M$. There is a set of reals $A$ such that any set $x$ can be injected into $A^{<\omega}\times\gamma$ for some ordinal $\gamma$ (see for example Lemma 5.25 in Jech's The Axiom of Choice). So any set can be injected into $\mathbb{R}^{<\omega}\times\gamma$ and indeed into $\mathbb{R}\times\gamma$ for some $\gamma$. Thus to prove the theorem it is in fact enough to strengthen Joel's theorem and prove that every subset $X$ of $\mathbb{R}\times\gamma$ admits a rigid binary relation. The proof is really just a slight tweaking, but I'll write it out. Let $ < $ denote the lexicographical ordering on $\mathbb{R}\times\gamma$ inherited from the two usual linear orderings on the component sets. (I identify $\mathbb{R}$ with Cantor space $2^\omega$).

Case 1: $X$ has no countably infinite subset. Then $ < $ restricted to $X$ is rigid, as any nontrivial permutation allows us to iterate the map countably many times on some moved element and get a countable subset.

Case 2: $X$ has a countably infinite subset $z_0,\ldots z_n,\ldots$ (and grab some other point $z^* $). Let $Z=\{z^* ,z_0,\ldots z_n,\ldots\}$. We define a rigid binary relation $R$ as follows. We set $R(z^* ,z^* )$ and put $z_0,\ldots z_n,\ldots$ below $z^* $ in ordertype $\omega$. Let $s_0,\ldots s_n\ldots$ enumerate the finite binary sequences. Then for $\langle x,\alpha\rangle\not\in Z$ we put $R(z_n,\langle x,\alpha\rangle)$ iff $s_n\subseteq x$. For $\langle x,\alpha\rangle$ and $\langle y,\beta\rangle$ both not in $Z$ we let $R(\langle x,\alpha\rangle,\langle y,\beta\rangle)$ hold iff $\langle x,\alpha\rangle<\langle y,\beta\rangle$.

We claim that $R$ is rigid. Let $\pi:X\rightarrow X$ be an $R$-automorphism. As in Joel's proof it is easy to see that every member of $Z$ gets fixed, and that as a result that whenever $\pi(x,\alpha)=(y,\beta)$ we must have $x=y$. It easily follows from this that $\pi$ fixes the second coordinate of every member of $X\setminus Z$ as well, as now $\pi$ restricted to the second coordinate is an automorphism of a subset of $\gamma$, with respect to the usual well-ordered relation on $\gamma$.