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.
One of the usual ways of proving in ZFC that every compact
Hausdorff space $X$ without isolated points (perfect
space) is
uncountable is by proving that there is a copy of the
Cantor space $2^\omega$ inside it, as follows. Pick two
points and separate them with neighborhoods $U_0, U_1$
having disjoint closures. Inside each of these
neighborhoods, pick two points and separating neighborhoods
$U_{00},U_{01}\subset U_0$ and $U_{10},U_{11}\subset U_1$
having disjoint closures inside those neighborhoods, and so
on proceeding inductively. Every infinite binary sequence
$s\in 2^{\omega}$ determines a unique nesting sequence of
these sets, which must be nonempty. And so we have
continuum many points in $X$, so it is uncountable.
This proof, however, makes several uses of the axiom of
choice. First, we have the choices involved with picking
the points to be separated, and second, the choices
involved with picking the separating neighborhoods.
Although there are only countably many choices being made
here, this is an instance of Dependent
Choice,
a stronger principle than mere countable choice, since the
choices are being made in succession. Finally, third, a
subtle point, we have the choices involved in picking for
each binary sequence a single point from the intersection
of the corresponding nested neighborhoods. After all, there
could be many points in that intersection.
With some additional assumptions on $X$, however, we can get around
these uses of choice, and thereby obtain answers to some of your questions. For example, if we only aim to prove
that $X$ is noncountable, rather than uncountable, then we
may assume towards contradiction that $X$ is countable, which provides for us a
canonical way of picking points from the space. (In the
case of the first use of choice, it would suffice if $X$
were separable, since we could just pick points from a
fixed countable dense set.) If $X$ were a metric space,
then we have a canonical way to pick neighborhoods of any
given point. Also, by making these neighborhoods shrink to $0$ as
the construction proceeds, we ensure that the intersection
of the nested sets contains a single point.
Thus, this argument shows in ZF, without any choice, that
every compact Hausdorff metric space having no isolated
points is noncountable. More generally, it shows, again without any choice, that every separable compact Hausdorff metric space without isolated points has uncountable size at least continuum.
If we have Dependent Choice, then we can prove that every
compact Hausdorff metric space is uncountable of size at
least continuum, since DC allows us to overcome the first
two uses of choice (picking the points and the
neighborhoods), and by shrinking the neighborhoods we avoid
the need for choice in the last step.
A clever person may be able to
improve these arguments to cover additional cases.
Meanwhile, let me mention an interesting example on the other side of the question. This example illustrates that several of the usual equivalent formulations of compactness are no longer equivalent in the non-AC context. Namely, it is consistent with ZF that there is an infinite but Dedekind finite set $D$ of real numbers. That is, $D$ is infinite, but has no countably infinite subset. It follows that $D$ has at most finitely many isolated points, since otherwise we could enumerate the rational intervals and find these isolated points, thereby enumerating a countably infinite subset of $D$, which is impossible. Let us simply omit these finitely many isolated points and thereby assume without loss of generality that $D$ is an infinite Dedekind-finite set of reals having no isolated points. Since $D$ is Dedekind-finite, every sequence in $D$ has only finitely many values and hence has a convergent (constant) subsequence. Thus, $D$ is a sequentially compact set of reals. In other words, $D$ is a sequentially compact metrizable space with no isolated points. However, $D$ is not uncountable in the sense you mentioned, since we don't even have $|\mathbb{N}|\leq D$, as there is no countably infinite subset of $D$. Nevertheless, $D$ is noncountable.
Best Answer
ZF alone does not prove that every PID is a UFD, according to this paper: Hodges, Wilfrid. Läuchli's algebraic closure of $Q$. Math. Proc. Cambridge Philos. Soc. 79 (1976), no. 2, 289--297. MR 422022.
One result in this paper is the following:
By the way, I didn't know the answer to this question until today. To find the answer, I consulted Howard and Rubin's book Consequences of the Axiom of Choice. (Actually, I did a search for "principal ideal domain" of their book using Google Books.)