aaron, you have been given some good guidance in the comments by EEAA and others. I would like to submit this as the answer that may best align with what you need. It is not guaranteed to help. I will explain what the un-addressed risks are afterwards.
Capture a complete backup, mirror, image, what-have-you of the entire VPS server instance.
1.a. Also capture a complete backup of JUST the web-app related files, databases, etc. Make sure you have a copy, and a copy of the copy. In essence, be prepared.
Request HostGator completely blow away, delete, remove, purge, scrub, whatever your VPS instance. Have them stand up a brand new pristine instance with the appropriate network settings. I would recommend against rolling back to a previous snapshot, if they offer something like that. Destroy the existing instance and get a fresh one.
2.a Recreate any system and user accounts, but USE DIFFERENT/BRAND-NEW AUTHENTICATION TOKENS, i.e. different passwords, certificates, etc.
Reinstall FROM SOURCES, not from your backups, webserver, webapp packages, and any other required software.
Re-implement the webapp on the brand new VPS instance. (Copy the webapp directory structure over from the backup. Will likely require a lot of config cross checking, but should be easier than rebuilding the whole thing from scratch.)
If you get really, really lucky, profit.
The problem with this scenario is that it assumes the compromise to the VPS was somewhere within the system itself and not the webapp. In all likelihood, the webapp and/or webserver are what was compromised and allowed the unauthorized parties in. This is the case in a very large majority of external technical exploits to Internet connected systems. There is a big subset of the Security industry making money hand-over-fist consulting, scanning, and fixing webapp vulnerabilities across the Internet.
Now, if they used the webapp as the channel but exploited and compromised a local user account, then the new authentication tokens (you DID implement new auth-tokens like I said, right!?) will buy you SOME time. But if they did it once, they can probably do it again.
In all honesty, it is probably better to rebuild the server from scratch, and re-install the webapp from scratch, creating new configuration files for the webapp and re-populating any data from the backups. You will also want to do some THOROUGH webapp testing (see my previous bit about webapp scanning) and probably some code review. Management will likely not appreciate the costs this may incur, but then they have to decide if its okay to be pwned, or not.
As EEAA said, good luck, and I don't envy the position you've been handed. However, the good news part is you can't be blamed for CAUSING the problem... right? =)