If you can get memcache properly installed, that will help the most as it will shift queries from the cache tables in the db to your memcache server.
Try these 3 things (in order of importance):
Set the transaction isolation level to Read Committed - https://drupal.org/comment/8437127#comment-8437127 (look in your settings.php for the insertion point; it will be after the $databases variable has been set with the database credentials). This is helpful even if using memcache.
$databases['default']['default']['init_commands'] = array(
'isolation' => "SET SESSION tx_isolation='READ-COMMITTED'"
Change your semaphore table to memory - https://drupal.org/comment/8469889#comment-8469889 (use the first code block "Have the name value be a primary key"). Note that this might not work if you are using MySQL 5.0 or lower due to BTREE indexes not working in Memory tables. Also noted that if you are using the memcache version of lock.inc this will not help.
ALTER TABLE semaphore ENGINE = MEMORY;
ALTER TABLE semaphore DROP PRIMARY KEY;
ALTER TABLE semaphore ADD PRIMARY KEY (name, value) USING BTREE;
ALTER TABLE semaphore ADD UNIQUE name (name) USING BTREE;
ALTER TABLE semaphore DROP INDEX value;
ALTER TABLE semaphore ADD INDEX value (value) USING BTREE;
ALTER TABLE semaphore DROP INDEX expire;
ALTER TABLE semaphore ADD INDEX expire (expire) USING BTREE;
Apply this core patch - https://drupal.org/node/2193149 This will help to reduce database deadlocks from occurring only after the above 2 have been done. If using memcache this core patch will not help as this fixes an issue when using the database as a cache backend.