I did this about a year or so ago and it is a difficult proposition. We moved from a rank structure with a fair reduction in overall ranks but a fairer overall system. The old system was based on achieving certain numbers of specific tasks, whereas the new one was completely points based via a weighted formula. This was a big program of work and was rather more seamless than I had thought it would be to implement.
My method was to setup all the new ranks in their correct positions with the formula in place but one that included an extra parameter for a role nobody had been granted (thus making them unattainable ranks).
I did NOT turn of rank notifications but rather, starting at the topmost rank, edited each one to remove the extra parameter. This meant that all users received a single notification for the highest rank they were able to achieve (it drove quite a bit of traffic in the first week) rather than everything happening by stealth.
By enabling them at the correct position I didn't need to delete the old structure right away and could revert back if the world fell in (it didn't). An alternative using your method (new ranks at the bottom) is to move the position of the new ranks above the old ranks one by one rather than deleting. This would achieve much the same result as my method but I was wary about someone, somehow, earning a new rank ahead of time.
I also posted an announcement the day before letting members know it was coming and briefed our superusers so they could deflect questions about the change on the day.
Something else you may want to consider is ensuring that there is no way to translate old rank to new so members dont feel they are being 'demoted' to a lower rank.
To answer your other questions;
Is there any way to easily backup the current rank structure in case we need to do a rollback?
Not if you delete them but you could if you keep them at the bottom as I have mentioned (ensuring that at least one of your new ranks is awarded immediately to new users as you don't want people getting old ranks).
Is there a way to export the ranking structure from Stage and import it on Production?
God, I wish it could but no.
What do you usually test during your QA phase?
On top of testing the overall look/feel I tested the ranking process itself. At the same time the new ranks released a new UI that shows a progress to next rank was put in place so I needed to know it was showing correct %-ages.
This was done by taking a bottom rank user and artificially ranking them up via granting mass kudos (you can change your kudo weight into the 1000s to accomplish this).
Our superusers have an icon next to their username. Is there a way to do that without duplicating each rank and adding a role as a condition for the 'superuser' rank?
Nope, we also have the same and there is no easy way out. However, I only duplicated the top 7 ranks as the lowest rank superuser had that rank. When a new intake of superusers occurs (ours is an annual program) part of that process is to check and make sure a lower ranked user is not being inducted.
