Seems to me you are passing on the hands on.
There is a ton of info you can use before replacing the cat.
Fact is, engine fails on emissions. Seperate the way they measured that or what they tell you, your engine is putting out more poisenous gas then your government allows you to.
This also means it can be easy or hard to fix. Expect hard. Especially when you have no idea of how good your ignition system is, don't replace vacuum hoses and believe in bad gas.
Besides the stuff you can try to do yourself, it is really up to you where you would like to start. Also, because nobody here can see your sparkplugs, rotor, cap, and cables and hoses really even better to diagnose over the internet.
An engine needs fuel, air and spark. Let's start with spark. Replace all cheap parts of the ignition system, plugs, rotor, cap. If you have, replace coil cable to. Suspects in bad ignition are cabling (expensive) coil (expensive)
I'm really cutting corners, because there is more to check. Would lengthen my post. Also, we don't seem to get diagnosis info, from you, after all the information, it didn't filter very well?
Vacuum, replace all hoses that are not new, usually the smaller diameter hoses close to the engine/ valve cover, suffer most. This won't fix your issue but it will help a bit. Same deal as running clean gas and heating the cat.
Compression. I just say engine is fine, but maybe your valve cover showing leaks, check for oil leaks, let us know.
Fuel. Too hard for now.
You can choose 3 things, which I believe is best on any give owner with failed emission engine:
Refreshen ignition
Replace vacuum hoses around valve cover and oil catch can and FPR the least.
New filter for more air. (only will help a bit)
I wouldn't recommend an oil change.
If that doesn't work, I would check MAF and lambda first myselve. But you should start thinking about a not so great catalyzer.
Tell this to your mechanic
And let us know :P