Maintaining order in a list in $AC^0$ in $O(1)$ time
Yes!

Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.

See also exercise 8.12 from open data structures and Roura's "A new method for balancing binary search trees".