Purely(ish) functional data structure with fast append and forward iteration
You're quite right that the "queue = two lists" approaches don't give you the running time you want when you have the ability to re-use earlier versions.  To get O(1) running time (amortized or worst case), you need a way to reverse the rear list and append it to the front list incrementally.  Instead of doing the reverse&amp;append all at once, taking O(N) time, you need to be able to do just a few steps of the reverse&amp;append every time you add a new element or remove/traverse through an element.

Hood and Melville showed one way to do this back in 1980.  For your purposes, their approach would be straightforward to adapt to C (with reference counting).  

In the early to mid 90's, I showed several ways to do this, some in O(1) worst-case time and some in O(1) amortized time. Most of these ways depended on lazy evaluation, which initially might seem hard to do in C, but in fact, there are only a very small of "shapes" needed for the lazy evaluation, each of which would be easy to represent using an ordinary node in C.

For example, a "Rotate" node has pointers to three sublists: L, R, and A.  Doing one step of the rotation replaces the "Rotate" node with an ordinary list node containing the head of L, and a pointer to a new Rotate node containing the tail of L, the tail of R, and the result of adding the head of R to the front of A.  Making this translation into explicit Rotate nodes instead of using generic lazy evaluation also means that you get O(1) worst-case bounds instead of O(1) amortized bounds.