Is this language recognizable by a 3 symbols TM in O(n log n)?
Can't you use the same idea as what you have for the case of 4 symbols, with the following modifications:


Always process a pair of symbols simultaneously.
In your "div 2" sweeps, mark a two-symbol block as "processed" by mapping $(00, 01, 10, 11) \mapsto (\epsilon0, \epsilon1, 0\epsilon, 1\epsilon)$. You still have $\epsilon\epsilon$ available as a "separator" that you can use at both ends, and you can recover the original data easily.
Use a similar trick for "mod 2" steps.


In general, you can squeeze in arbitrarily large amount of bookkeeping information with the help of the third symbol by processing $O(1)$ symbols at a time.