You are going in the wrong direction completely. If your site is slow, don't "fix" it with a cache, fix it by fixing it.
Redis cache as backup for FPC
Redis is a cache store, it won't make a site any faster, it will just improve performance of content fetched from the cache. The process of fetching from the cache isn't slow to begin with, file based caching is fast enough to not be a bottleneck, Redis won't change that (NB. Don't use file based caching, it is broken, Redis is a solution to fix another issue with cache swelling, so keep it - but it won't help your speed).
mysql primer and added all improvements
Why? Its a great utility (along with mysqltuner), but it isn't a miracle worker. The best it can do is analyse data based on what it has seen - not make an accurate or intelligent human decision as to what the bottleneck might be. Following scripts blindly like this, without understanding the consequences of what you are changing will almost certainly lead to problems and by no means give you the performance boost you seek. It could very possibly reduce performance, not improve it.
emptied cache, locks, sessions
We've been over cache != speed - but what were you expecting to happen after clearing the cache? It would obviously be slower as a result of an empty cache.
Lock files are entirely unrelated to speed, they are empty files, created during a reindex to prevent it running twice (simultaneously) over itself. FYI. Not once in 6 years have I removed a lock file in any situation.
Deleting sessions. Well, worst case, it actually makes the site faster, and then you are faced with the dilema of a fast store that never has sessions (and thus no sales) - or a slow site that people can buy from. As a diagnostic step, its going to give no tangible/reliable results. Don't delete sessions in any circumstance, ever.
running daily clean scripts for log tables and such
Housekeeping won't improve performance, especially if the site has no traffic/logs to clear down. Its certainly good practice, but isn't your issue.
Fundamentally, the issue comes down to two things.
If your hosting is improperly configured (which from the sounds of things, it is, given the DIY tuning of MySQL), it will dictate the baseline for performance. Your store can only ever be as fast as the infrastructure underneath it. No amount of application level tuning will fix that. Easiest way to tell is to install a demo store with sample data - and see what the performance is like. If that's slow, there's your issue.
The second issue is less clear, but not impossible to fix. Its a case of profiling your code to find the bottleneck and fix it. Start by restoring the default theme, then disabling modules one by one until speed is normal again. That's a fairly high level approach, but it will certainly get you going.