I don't use Mint, but I suspect you're having the following problems if you don't have HW accel with the KMS driver:
you haven't blacklisted Catalyst, or you're on the wrong radeon (check glxinfo for what the system is using for what)
You haven't manually updated. Mint will by default only update the bare necessities, it will not update all of the packages, and it doesn't start out as a bleeding edge distro, so you'll have to do manual updates to get a representative system. It's one of the biggest problems with Mint, I don't know why they're not changing it. The problem with Mint is that since most of the user base only does the automatic updates, there is not enough testing feedback for the full updated systems as they should be running, and therefore Mint isn't the most bug free of distros, but if you want to have the best chance of everything working as it should, update everything that is updateable, including - very important - the kernel itself. You really don't want to run on an "oldish" kernel. Either you're running on a really old long term support kernel, and you're using all of the patches and proprietary bling, or you're running on a bleeding edge kernel that has all of the latest updates and functionality. In any case, only use Catalyst if you really have to, like if you really need the few functions or extra fps that Catalyst offers over radeonsi. Catalyst is end-of-line for linux, it's not developed further, as AMD is switching to AMDGPU as proprietary KMS driver on linux, and is focusing completely on the development thereof, and on the development of radeonsi. AMD is just not paying a whole lot of attention to porting the Windows driver to linux much longer.
If you're 100% sure that you're running ONLY on the open source driver, and you're still experiencing stuttering, and dmesg is not informative on what is happening, and you've not been experimenting with your scheduler or have been tweaking some holy grail kernel settings proposed by some guy on a forum (ya know, Ubuntu and Mint fora... sigh...), the first stop is to run top/htop and take a look at what the system is doing at any given time. If that doesn't help you, run powertop to see what part of the system is using power, that is often also indicative. Often stuttering in systems is caused by crooked power management settings. Powertop will make recommendations for efficient power management, but you have to let it learn for at least 20 minutes or so, or the recommendations may have adverse effects, for instance with USB devices being shut down where they shouldn't be. Also run the storage diagnostics in disks. Sometimes stuttering is caused by storage problems.
There are a few things that can screw a system up, that are often overlooked: Google Chrome for instance being the number 1, because it makes ample use of background processes and interferes with a lot of parts on the system. Just don't ever use Chrome on Linux, use Chromium, use the pepper hack to get flash support if you really have to, use Firefox, but just don't use Chrome lolz, it is only maintained by a dude from Google for Ubuntu, but nothing else, whereas Chromium is maintained by the maintainers of the different distros, and is much more stable on most distros. Google is infamous for not playing nice with code. Their code is a mess, they don't even try to respect the open source principle of using existing packages developed by others, they just hack them and provide their own version with their crap to make it work willy-nilly, and that often leads to all kinds of problems.
For firefox, the problem might be that your system doesn't play well with the latest version. If you're having Firefox performance issues, switch to the extended support version of Firefox. It's much more stable on intermediate systems (not bleeding edge and not really old) than the latest version, and just as secure (in fact, more secure, it's the enterprise version basically).
I think you have been trying out too many things. That's not criticism, everybody has that, it's when you look over something and don't give up on solving it, and it happens to all of us. Just don't waste too much time on it. If you're on Arch or Gentoo, you have to do a lot of diagnostics and problem solving, but not if you're on Mint. It may very well be that your install was compromised in some way or another, because of a crooked package or something. There is no way to know without full system diagnostics, and most of the time, it isn't worth it. You can however easily reinstall without losing your data or applications, by installing without formatting the /home partition. Maybe try a standard install without Catalyst, see if that solves the problem. It's only 5 minutes work, and can save a lot of time. I would probably just do that to be honest. Part of the problem with Mint is that nobody's listening, just like with Ubuntu, if it's a fundamental problem, you'll just never know, and all you have to go on is the ramblings of other people on their forum, people that are equally in the dark. At least on Ubuntu there are alternative community fora that may offer useful information, like askubuntu for instance, but for Mint there is nothing like that.
I'm sorry I can't really help you, I don't have enough info, and it's even hard to help out on a distro one doesn't know when full system debug info is available.