I would personally pull all the data from the various locations (/etc /usr/share, etc) to my local machine and do a fresh install. Replace as possible/as needed the data from the configuration files, and "fix" the rest. If you are looking for zero downtime, you may want to look at doing a chroot'd install on a separate disk (requires someone local to the remote location to install an new disk) or a local install (if architectures are similar enough) and testing it all out, then once it's all ready, point the bootloader to the new drive, install the new kernel and go. Once you are up with the updated OS, you will probably find some overlooked problems; iron out as necessary. You could probably update your bootloader at that point as well to give it a fully "cleaned" feel.