Necessary and sufficient conditions for the existence of a utility function
The following is essentialy due to Debreu. The result is formulated in terms of linear orders, but each complete and transitive relation induces a linear order on the indifference classes:
Theorem: Let $S$ be a set and $\preceq$ be a linear order on $S$. Then $\preceq$ has a utility representation if and only if there exists a countable set $C\subseteq S$ such that whenever $x\prec y$, then there is some $c\in C$ such that $x\preceq c\preceq y$.
Proof: To see that the condition is necessary for the existence of a utility representation, let $u$ be a utility representation of $\preceq$. Call $(x,y)\in S\times S$ a jump if $x\prec y$ and there is no $z$ such that $x\prec z\prec y$. We show that the set of jumps is countable. Clearly, if $(x,y)$ and $(x',y')$ are both jumps, then $\big(u(x),u(y)\big)$ and $\big(u(x'),u(y')\big)$ are disjoint intervals of real numbers. Each such interval contains a rational number, so there is an injective function from jumps to rational numbers and so the set of jumps is countable. Let $J$ be the set of all elements of $S$ that occur as the first or second coordinate of a jump. Clearly, $J$ is countable too. Let $$Q=\Big\{(q_1,q_2)\in\mathbb{Q}\times\mathbb{Q}:q_1&lt;q_2, u^{-^1}\big((q_1,q_2)\big)\neq\emptyset\Big\}.$$ The set $Q$ is countable. For each $(q_1,q_2)\in Q$, choose some $s\in  u^{-^1}\big((q_1,q_2)\big)$ and let $B$ be the set of such $s$. $B$ is also countable and we can choose $C=B\cup J$.
Now we show that the existence of such a set $C$ is sufficient for the existence of a utility representation. Without loss of generality, we can take $C$ to be nonempty and write $C=\{c_0,c_1,\ldots\}$. Now define $u$ by $$u(x)=\sum_{n:c_n\preceq x}\frac{1}{2^n}-\sum_{n:c_n\succeq x}\frac{1}{2^n}.$$
$\square$
A comprehensive source for all things existence of utility functions is the book Representations of Preferences Orderings by Douglas S. Bridges and Ghanshyam B. Mehta.