We did this exact type of work many times in the LTN systems located in most major cities with manhole and duct systems. I would suggest you purchase a pre-cast manhole,
http://www.utilityconcrete.com/Handholes?catid=26#!, and install it such that the incoming line is on one side of the new manhole. If using precast, you will have to dig a hole both under and around the existing duct to allow for maneuvering the precast in place. We would under dig the duct, the hole to one side was as big as the hole to be placed around the existing duct, pour a new concrete pad. This pad becomes the slide pad to move the lower half of the manhole in place. Cut the necessary notches on the upper half and lower it into place.
No cheap and not easy, but since yo do not take an LTN out of service, an option. Last of course, build a new manhole around the existing duct work. Consider that cost versus taking an outage or running a temporary over-ground supply. (Cheapest option if you must remain in service.)
Hope this helps,
Newton Law