Sew on loops or modify what is left of the existing shock cord into a loop on each side and use the loops to tie in sacrificial cord. Another alternative would be to study the method used by Dirty Girl Gaiters and adapt that to your pair (http://www.dirtygirlgaiters.com/job.html) and buy a pair when yours are shot :)
I think it is a more modern trend to have permanent arch straps on gaiters. That might be practical for use on snow with crampons taking the brunt of the punishment, but it doesn't make sense to me to use a design like that on rocky trails where they are going to be abraded. You want to eliminate them (as with the Dirty Girls) or make them easily replaceable. My older MontBell Stretch gaiters have small diameter shock cord tied to a loop on one side and run through a tough fabric flap on the other that acts like a toggle to tighten them. The newer model uses shock cord inside a polymer channel to help protect it a minimize wear (http://www.montbell.us/products/disp.php?cat_id=91&p_id=1129415). You could borrow from that and use some sort of plastic tubing, but with light shoes I think you would feel the lump. Paracord or even the paracord outer jacket will last quite a while-- depends on you mileage and conditions, of course. I haven't tried it, but some tough coated Spectra based stuff might be interesting-- you don't need much.
With the loops, you can use any kind of line you like and if it fails, it can be easily replaced on the trail--- you do carry spare line, right? :)
Here is the MontBell approach. Note the webbing loop on the top gaiter with the shock cord tied to it. The bottom one shows the laminated fabric lock to form an adjustment for the other end of the shock cord. That could just be another loop, or a toggle with a webbing slot in it, etc.