I have had another thought on ground freezing in your situation. Remember that water expands on freezing, and consider what effect that expansion will have on the existing structural elements, such as the column bases! Beware also of tying back into the existing Interstate embankment, because this is what supports the bridge abutment (if I have understood you correctly).
I think the main problem is probably the temporary support of the excavation. If the excavation were supported, I guess you could design a retaining wall system which could be built in the available space.
Have you considered contiguous bored piles installed with a low-headroom rig. The piles would have a capping beam. You would excavate shallow depths at a time over short lengths only. On excavation, you would line the wall with sprayed concrete (although some provision would have to be made for the drainage of water, but not soil, at intervals from behind the wall).
You may have to anchor the wall back at one or more levels (remembering my caution above). This may be possible if the bridge abutment is not piled. You could use multi-strand anchors, which do not require much headroom to install. However, I do not know what - if anything - is available to anchor into.
You could design the retaining wall system so that the "temporary" contiguous bored piles act as permanent works, rather than forming a separate retaining system.
I suggest you consult a specialist geotechnical engineer, who will have a chance to see your drawings and visit the site. It sounds like the scale of the project would justify this expense as part of a sensible risk management strategy. (If there had been no risk, we would not have heard about this job.)