NOTE: The steps described below are not intended to be vendors approved fix practice. It is basically dirty hack and may lead to total MySQL data loss!

Symptoms:

1. Most likely there was cold restart on VPS prior the issue appeared
2. MySQL not starting

3. MySQL log

   /var/lib/mysql/hostname.err

   is full of errors related to InnoDB and even pieces of core dump code

Solution:

1. Ensure MySQL stopped, if not then stop it.

2. Backup ENTIRE /var/lib/mysql directory to somewhere

3. Enable InnoDB forcing recovery placing the line 

   innodb_force_recovery = 4 to /etc/my.cnf

4. Start MySQL (if not starting you can play with numbers from 1 to 6 in above line)
5. Do initial checks via

   mysqlcheck -A --auto-repair

   , (don't panic if it cannot finish full checks)
6. Do the full dump of DBs:

   mysqldump -A > dump.sql

7. Stop MySQL
8. Comment out the

   innodb_force_recovery in /etc/my.cnf

9. Remove

   /var/lib/mysql/ib*

10. VERY DANGEROUS! Remove all *.idb files inside of mysql directory:

    find /var/lib/mysql -type f -name "*.ibd" -delete

11. Start MySQL
12. Fill the MySQL with dump created in step 6:

    mysql < dump.sql

13. If the dump will stop with error "cannot create database" then drop that database in mysql and repeat filling the dump.
14. If the dump has errors regarding 'duplicate entry for key' you will need to run the restore with --force

In ideal conditions it will fix problems.