Tearing out and rebuilding stair seems like a lot of work. I was trying to think of a way around that...and it's actually an idea I've done before when building a deck. The off-the-shelf stringers had to be cut to handle the distance from the deck to the ground. Obviously this screwed up the bottom most riser distance. What we did is shimmed each tread a different amount to adjust them all to have the same riser distance.
So, for example, let's say you have 10 stairs. You've taken away 1.75" from the bottom most riser.
1.75"/10 = .175"
So, on the top most stair, you'd add .175" of material.
On the second top most stair, you'd add 2 * .175 = .35" of material.
And repeat all they way to the bottom most stair = 10 * .175 = 1.75" of material.
In the end, you've basically adjusted the riser of each step proportionally to make up the 1.75" that was taken away.
Granted, that may be a lot of work too, though should be easy to do if you happened to have a bench planer (maybe an excuse to get a bench planer!?)
Even without a planer, you might be able to 'round' each shim size to the closest dimensional lumber. So, .175 = 1/4" ply. .35" = 3/8" ply, etc.
So did that answer your question? Probably not. I guess I'm thinking it's best to have the stringers in contact with the slab, and since the current ones already do that, it'd be nice to not have to tear out the entire structure and replace.