There are two relatively economical methods to make a non-stage 3 airplane compliant to the stage 3 noise restrictions.
1. Install a hush kit that reduces the perceived noise level.
2. Reduce the operating weights of the airplane and/or use reduced flap setting to reduce the perceived noise level.
Re-engining is much more expensive and so far the DC-8-70 series (110 airplanes) has had the most success with this method. Would you believe that the '70 series will also meet the proposed stage 4 levels? Installing navigation and communication gear to meet the new requirements in those areas, especially in Europe, is the tough one for these birds.
The reason that I use "perceived" is that is how the rule is written. If you can either fly with a lower power setting for the same speed, fly at a higher speed for the same power setting, or climb out more quickly; your perceived noise level will be less. Also, engine out performance is checked; so a 3 engined airplane is easier to make stage 3 than a twin. i.e. 727 versus DC-9.