If your web server has a virus, the only safe thing to do is nuke in from outer space. That's right, put it onto the next space shuttle mission and make sure it's jettisoned far enough away from earth that we don't all get showered in EMP or fallout, and press the red button that makes it explode.
If that's unfeasable, too expensive, or you your local shopping centre has run out of nuclear bombs, then the only other way to make sure any virus is gone is to format the server. Your hosting provider may be able to assist you with this by setting up a 2nd VPS and giving you a month or so to move everything over before shutting down and deleting the current instance. Of course, if you just migrate everything over indescriminately from the old VPS to the new VPS then you'll likely bring the virus with you.
If you have customer data on there and there's a risk you're leaking that data or taking part in a botnet or a backdoor has been left in the system, then you have an obligation to your clients to do everything in your power, and simply scanning/removing any known virus isn't really enough because you just never know what they've left behind.
Regarding the backups, I would say you're doing the right thing, because you shouldn't have execute permissions on anything the public_html
folder and the database is unlikely to be harbouring anything malicious.