If possible get your PHP updated to the 5.4.x branch.
Before you add your caching layer you need to determine whats slowing down MySql and PHP.
You need to enable WP_Debug and eliminate any PHP errors. Look for undefined indexes, syntax errors and deprecated functions.
That 20 second to first byte is all PHP, MySql and or WordPress related. It sounds like a bad memory leak from poorly written code or extremely long query times. Do you have any expensive queries, e.g. meta_query?
I would recomend installing the Debug Bar and Debug Bar Extender plugins. Enable profiling and set check points at various parts of your templates like before and after any special queries.
To set a checkpoint use the function: dbgx_checkpoint( $note="" ) Use the $note variable to list where the checkpoint is installed.
The profiler will you record the run times and memory usage to pinpoint any problems.
It will also give you a clear picture of the object cache if your using a WordPress object cache plugin.
Also APC, eAccelerator, xCache will not all work at the same time and blow up your site if you try it (I’m sure you probably meant you tried each of them).