3 tables of a mysql database, each containing ~200 rows on a Redhat
Enterprise 3 remote dedicated server were accidentally deleted, and I
am looking for a solution to restore that data.

Unfortunately, no backups were kept either by us, or our server host,
and delivery of the media for restoration is not possible. We have
full SSH access to the box in question.

How is it possible to recover this data?

http://www.porcupine.org/forensics/
http://www.porcupine.org/forensics/tct.html
The pcat program here captures process memory, which may still
contain the required data.  Copying your database process to
an uninvolved regions of disk should be done before changes
or process termination prevent you from doing so.

And/or it may be on disk.
http://www.fish.com/tct/help-recovering-file
Although I've recovered file data before I've never tried database records
which might take some interpreting even when you find them.

Unfortunately, that would deal more if the data was erased from a
filesystem standpoint. With this, the data was properly (sic)
overwritten by the mySQL server.