I have solved the problem affirmatively at least for sets of reals.

Theorem. Every set of reals admits a rigid binary relation (with no use of Axiom of Choice). Equivalently, every set of reals is the vertex set of a rigid directed graph.

Proof. Suppose that $A$ is a set of reals. We may freely regard $A$ as a subset of Cantor space $2^\omega$. Let us break into several cases.

Case 1. $A$ is countable. This is the easy case, since we may simply impose a rigid structure on it by making it a linear order isomorphic to omega (or a finite linear order if $A$ is finite).

Case 2. $A$ is uncountable, but $A$ has a countably infinite subset. Fix such a subset $Z=\{z_0, z_1, \ldots\}$ and fix a point $z^*$ in $A-Z$. For each finite binary sequence s, let $U_s$ be the neighborhood in $2^\omega$ of all sequences extending $s$, so that $U_s(x)$ iff $x$ extends $s$. Clearly, the structure $(A,U_s)_s$ is rigid, since if you move any point $x$ in $A$ to another point, you will move it out of some neighborhood $U_s$ that it was formerly in. We now reduce this structure to a binary relation. Let $R$ be a relation on $A$ that places all the $z_n$ below $z^*$, ordered like $\omega$, and makes $R(z^*,z^*)$ true. Next, enumerate the finite binary sequences as $s_0$, $s_1$, etc., (this does not require AC). We define $R(x,y)$ iff $x=z_n$ for some $n$, $y$ is not $z_m$ for any $m$, $y$ is not $z^*$, and $U_{s_n}(y)$. That is, the first coordinate gives you some $z_n$, and hence some $s_n$, and then you use this to determine which neighborhood predicate to apply to $y$, but we only do this for $y$ outside of $Z\cup\{z^*\}$. I claim that the structure $(A,R)$ is rigid. The reason is that $z^*$ and the reals $z_n$ are definable in the structure $(A,R)$, and so they are fixed by all automorphisms. (The real $z^*$ is the only one such that $R(z^*,z^*)$, and the $z_n$ are the only predecessors of $z^*$ wrt $R$.) Since every $z_n$ is fixed, it follows that every automorphism must respect the neighborhood $U_{s_n}$ intersect $A$, and hence fix all reals. So there are no nontrivial automorphisms.

Case 3. Weird $A$. The only remaining case occurs when $A$ is uncountable, but has no countably infinite subset. (It follows that $A$ will be Dedekind finite, but not finite.) In this case, every permutation of $A$ will consist of disjoint orbits of finite length, since if there were an infinite orbit, then we could build a countably infinite subset of $A$ by iterating it. But if every permutation of $A$ is like that, then $A$ has no permutations that respect the usual linear order $<$ of the reals. Thus, $(A,<)$ is rigid. QED

In particular, it is not true that the usual counterexample to AC in the symmetric forcing models is a counterexample to this rigidity question. Those sets are sets of reals, and this argument shows that they have rigid binary relations, without being well-orderable.

I'm not sure how far one can extend this idea. How about subsets of $2^\kappa$ for any cardinal $\kappa$? I think, however, that even this still won't give a full positive answer for all sets.

nontrivialautomorhphisms. $\endgroup$