I have just spend three days on this nightmare. Ideally, you should have a backup that you can restore, then simply drop the damaged table. These sorts of errors can cause your ibdata1 to grow huge (100GB+ in size for modest tables)
If you don't have a recent backup, such as if you relied on mySqlDump, then your backups probably silently broke at some point in the past. You will need to export the databases, which of course you cant do, because you will get lock errors while running mySqlDump.
So, as a workaround, go to /var/log/mysql/database_name/
and remove the table_name.*
Then immediately try to dump the table; doing this should now work. Now restore the database to a new database and rebuild the missing table(s). Then dump the broken database.
In our case we were also constantly getting mysql has gone away
messages at random intervals on all databases; once the damaged database were removed everything went back to normal.