I think the following computable function shows that it is always possible (it chooses an order during queries):
Maintain a table, initially emtpy
As soon as (a <= b) is requested, see if a and b are already in the table (using the computatble equality function) , if so, use their ordering in the table. If an element is not in the table, add it.
Hence the table gives a consistent total order (it depends on which ordering queries are requested, but that is not relevant?)
This method has more than Gedanken value. Amusingly, I used it in "A killer adversary to quicksort" [Software - Practice and Experience 29 (1999) 341-344, http://www.cs.dartmouth.edu/~doug/mdmspe.pdf] to drive essentially any quicksort (illustrated with the C standard sort interface) into quadratic behavior. Doug McIlroy