Here is a simple example of size continuum. Do the ordinary middle-third construction of the Cantor set, except that whenever you delete the $n$-th (numbered by level and then left to right, say) middle-third interval leave in exactly $n$ points from that interval. Let's call the resulting set $X$. Any automorphism of $X$ must map (resp. left-, right-) isolated points to (resp. left-, right-) isolated points. Since we left a different number of points in each middle-third interval, the automorphism must fix every inner point of each middle-third interval as well as its two endpoints. By density, it follows that the automorphism fixes every point of $X$.
All of your examples are scattered, I checked the Rosenstein's Linear Orderings to see if he had anything good to say about which scattered linear orders are rigid. To my dismay, this is what I found: "These considerations seem to make impossible an inductive argument (on $F$-rank or $VD$-rank) to determine which scattered types are rigid." (p. 133) However, he does cite a result of Anne Morel (Ordering relations admitting automorphisms, Fund. Math. 54 (1964), 279-284.) which says that a linear order $A$ is not rigid if and only if $A \cong A_1 + A_2\times\mathbb{Z} + A_3$ for some linear orderings $A_1,A_2,A_3$, with $A_2$ nonempty.
Dense examples of rigid subsets of $\mathbb{R}$ would be interesting to see. This is probably not too difficult to construct under CH. But a ZFC example might have to deal with important barriers such as Baumgartner's result that All ${\aleph_1}$-dense subsets of $\mathbb{R}$ can be isomorphic, Fund. Math. 79 (1973), 101-106. Maybe there are some examples in this classic paper of Sierpinski Sur les types d'ordre des ensembles linéaires, Fund. Math. 37 (1950), 253-264.
All three papers can be found here.
Addendum (after sdcvvc's comment): For the sake of completeness, I'm including a simplification of the Dushnik-Miller argument that produces a dense subset $X$ of $\mathbb{R}$ which is rigid (though not the stronger result that $X$ has no self-embeddings).
To ensure density, the set $X$ will contain all rational numbers. Note that an automorphism $f$ of $X$ is then completely determined by its restriction to $\mathbb{Q}$. Indeed, since $f[\mathbb{Q}]$ must be dense (in $X$ and) in $\mathbb{R}$, we always have
$f(x) = \sup\{f(q):q \in (-\infty,x)\cap\mathbb{Q}\} = \inf\{f(q):q \in (x,\infty)\cap\mathbb{Q}\}.$
There are only $c = 2^{\aleph_0}$ increasing maps $f:\mathbb{Q}\to\mathbb{R}$ with dense range. Let $\langle f_\alpha:\alpha<c \rangle$ enumerate all such maps, except for the identity on $\mathbb{Q}$.
We will define by induction a sequence $\langle (x_\alpha,y_\alpha) : \alpha<c \rangle$ of pairs of irrational numbers. The $x_\alpha$ will be points of $X$ while the $y_\alpha$ will be in the complement of $X$. For each $\alpha$, we will have $f_\alpha(x_\alpha) = y_\alpha$ (in the sense of the inf/sup definition above).
Suppose we have defined $(x_\beta,y_\beta)$ for $\beta<\alpha$. Since $f_\alpha$ is not the identity, there is a rational $q$ such that $f_\alpha(q) \neq q$. Let's suppose that $f_\alpha(q) > q$ (the case $f_\alpha(q) < q$ is symmetric). Since the real interval $(q,f_\alpha(q))$ has size $c$ and the extension of $f_\alpha$ to all of $\mathbb{R}$ is injective, we can always pick
$x_\alpha \in (q,f_\alpha(q)) \setminus(\mathbb{Q}\cup\{y_\beta:\beta<\alpha\})$
such that $y_\alpha = f_\alpha(x_\alpha) \notin \mathbb{Q}\cup\{x_\beta:\beta<\alpha\}$. Note that $x_\alpha < f_\alpha(q) < y_\alpha$ so $x_\alpha \neq y_\alpha$.
In the end, we will have
$\{x_\alpha: \alpha < c\} \cap \{y_\alpha : \alpha<c\} = \varnothing$
and any set $X$ such that
$\mathbb{Q}\cup\{x_\alpha:\alpha<c\} \subseteq X \subseteq \mathbb{R}\setminus\{y_\alpha:\alpha<c\}$
is necessarily rigid since $f_\alpha(x_\alpha) = y_\alpha \notin X$ for each $\alpha<c$.
In ZF, the following are equivalent:
(a) For every nonempty set there is a binary operation making it a group
(b) Axiom of choice
Non trivial direction [(a) $\to$ (b)]:
The trick is Hartogs' construction which gives for every set $X$ an ordinal $\aleph(X)$ such that there is no injection from $\aleph(X)$ into $X$. Assume for simplicity that $X$ has no ordinals. Let $\circ$ be a group operation on $X \cup \aleph(X)$. Now for any $x \in X$ there must be an $\alpha \in \aleph(X)$ such that $x \circ \alpha \in \aleph(X)$ since otherwise we get an injection of $\aleph(X)$ into $X$. Using $\circ$, therefore, one may inject $X$ into $(\aleph(X))^{2}$ by sending $x \in X$ to the $<$-least pair $(\alpha, \beta)$ in $(\aleph(X))^{2}$ such that $x \circ \alpha = \beta$. Here, $<$ is the lexicographic well-ordering on the product $(\aleph(X))^{2}$. This induces a well-ordering on $X$.
Best Answer
Update: Joel and I have written an article based on the concepts introduced in this question, which can be seen at http://arxiv.org/abs/1106.4635
It looks to me that it is consistent with ZF that there is a set without a rigid binary relation. Use the standard technique for constructing such wierd sets. First construct a permutation model of ZFA where the set of atoms A has the desired property and then use the Jech-Sochor theorem to transfer the result to a ZF model. Any sentence that can be stated just using quantifiers over some fixed iteration of the powerset operation over A can be transferred. In our case the sentence "A has no binary relation without a nontrivial automorphism" only needs to quantify over say the fifth iteration of the powerset of A (probably less). The standard reference for these techniques is Jech's text The Axiom of Choice from 1973. (There the Jech-Sochor theorem is called the First Embedding Theorem).
In our case what is called the basic Fraenkel model is the desired ZFA model. (This and other similar models are constructed in Chapter 4). Suppose R is a binary relation on A. Then there is a finite set E (called the support of R in Jech's terminology) such that any permutation of A fixing E pointwise maps R to itself. In other words such bijections are automorphisms of R. Since E is finite we can without AC find nontrivial such bijections and it follows that R is not rigid.
In fact examining the proof of the Jech-Sochor theorem shows that Joel's fact about sets of reals is optimal in the following sense: models of ZFA are simulated by ZF models by transferring the set of atoms to a set of sets of reals and thus one cannot in ZF go any further up the hierarchy of types than the powerset of omega and hope to construct rigid binary relations.