The building could have been supported on a balanced mat foundation under a basement where the weight of the excavated soil is greater than the weight of the building. In the 19th century, brick and timber buildings several stories tall were built in downtown Omaha with the basements extending to the curb under wide sidewalks. Continuous footings supported the walls. The underlying soil was saturated loess (silty clay) with an apparent preconsolidation pressure only about 500 pounds per square foot greater than the existing overburden pressure. Some of these buildings were warehouses. Some still exist.
The extended basement helps, because the pressure influence of an excavation on both sides of the wall is twice the effect of an excavation on only one side. You can take permanent advantage of this by building a basement wall near the outer edge of the trench and roofing it over with a concrete patio. This may allow you to use wide strip footings rather than a continuous mat, which will be harder to build in pieces.
The trick is to get this basement and footings in place while maintaining support for the building. One way might be to dig broad trenches outside and inside a length of a wall, staying far enough away to maintain the bearing capacity for the existing footing. Build temporary footings (say, wooden mats) in the trenches, lay up timber cribs for columns, dig shallow trenches under the footing, and underpin the footing with needle beams supported on the cribbing. Excavate the soil between the trenches, build a permanent footing below the existing footing, lay up the section of basement wall, and fill the gap with dry-packed concrete. Move down the line and repeat until you have all the walls extended down to basement level.
If the bearing capacity is too low, dig trenches several feet deep under the new footings and fill with well-compacted granular soil. Perhaps the weathered rock will be suitable. Or use lean concrete.
Perhaps the rent for the basement space can pay for the work.
If the groundwater table is shallow, the work will be more difficult.
You need a good geotechnical engineer, a structural engineer, and a very careful builder.
Good Luck