Are there any other rational preference relations without utility function representations, besides Lexicographic?
Yes, there are many. Here are some examples :

Consider the weak preference relation $\succsim$ defined over $\mathbb{R}^2$ as:


Example 1  


$(x_1, y_1) \succsim (x_2, y_2)$ 

if and only if 

either ($x_1+y_1 &gt; x_2 + y_2$) or ($x_1+y_1 = x_2 + y_2$ and $x_1 \geq x_2$)

Claim : $\succsim$ cannot be represented by a utility function.

Proof : Suppose by contradiction that there existed a utility function $u$ representing these preferences. For each $a &gt; 0$, we have $(a, 0) \succ (0, a)$, and therefore, $u(a, 0) &gt; u(0, a)$. We can therefore assign to $a$ a non-degenerate interval of values satisfying the above inequality
$I(a) = [u(0, a), u(a, 0)]$. For any $a &gt; b &gt; 0$, all commodity bundles generating utilities in the interval $I(a)$ are strictly preferred to those in the disjoint interval $I(b)$ and should therefore be assigned a greater utility level. Then in each of these intervals we can pick a distinct rational number in increasing order to represent preferences. Since $a \in \mathbb{R_{++}}$, there are uncountably many such intervals, but set of rational numbers are countable. This results in a contradiction.


Example 2  


$(x_1, y_1) \succsim (x_2, y_2)$ 

if and only if 

either ($\min(x_1,y_1) &gt; \min(x_2,y_2)$) or ($\min(x_1,y_1) =  \min(x_2,y_2)$ and $x_1+y_1 \geq x_2 + y_2$)

Claim : $\succsim$ cannot be represented by a utility function.

Proof : Suppose by contradiction that there existed a utility function $u$ representing these preferences. For each $a &gt; 0$, we have $(a+1, a) \succ (a, a)$, and therefore, $u(a+1, a) &gt; u(a, a)$. We can therefore assign to $a$ a non-degenerate interval of values satisfying the above inequality
$I(a) = [u(a, a), u(a+1, a)]$. For any $a &gt; b &gt; 0$, all commodity bundles generating utilities in the interval $I(a)$ are strictly preferred to those in the disjoint interval $I(b)$ and should therefore be assigned a greater utility level. Then in each of these interval we can pick a distinct rational number in increasing order to represent preferences. Since $a \in \mathbb{R_{++}}$, there are uncountably many such intervals, but set of rational numbers are countable. This results in a contradiction.