For the misfire - try swapping coil on plug packs - see if the CEL follows the cylinder or the coil on plug pack.
Getting a P0420 code with a new replacement cat sounds like the downstream O2 sensor (after cat) is reading poorly or dying. Replacing it may or may not fix the CEL - depends on a number of factors. Might be able to trick it with the sprak plug defouler trick - basically pulling the downstream O2 sensor away from the exhaust stream - making it read a little differently. That would be the least expensive/quickest way to see if it will get around the P0420 code.
The other strange behavior - I'd look at cleaning the MAF sensor and throttle body first. Check for obvious damage to the airbox, tubing leading to the throttle body, any missing or loose vacuum hoses. Might also try cleaning the IAC valve - little tougher to get at, but worth cleaning in hard to diagnosis situations. The symptoms you are describing sound like a classic vacuum leak. Could be a leak around the induction system (airbox, throttle body, intake manifold, EVAP system, etc.) - could also be a leak in the exhaust system, either right at the front pipe where the exhaust manifold runs to the pre-cat, or close to the O2 sensors.
There is also a low probabiliy that all this is caused by a faulty coolant temperature sensor or faulty chassis ground/EMI/RF noise. Incorrect coolant temperature reported to the ECM can cause misfires and screw up the air/fuel mix enough to trigger a P0420 code. Electrical noise can cause all sorts of problems, many are hard to troubleshoot as they jump around to seemingly unrelated systems. The coolant sensor is on the right side (driver's side) of the engine - right behind the radiator hose, has an electrical connector with brown and white wires running to it. There is also a radio setting condenser (capacitor) that helps limit EMI/RF noise in the ignition system right behind it - might be a good idea to check those connections, the capacitor - just have to replace it to test, the coolant sensor - you can check if you have a mutlimeter handy. Toss it into water, heat it up and see that the resistance changes (temp goes up, resistance goes down).