What could it be?

No more exhaust leaks. No vacuum leaks. Timing has now been perfectly set. New ignition components (cap/rotor/plugs/wires).

The only thing that hasnt been changed in a while is the O2 sensor, but it's a 4G63 8V SOHC engine, so the O2 is supposedly a closed loop system.

There's just a fair bit of soot in the exhaust, and you can hear backfiring when downshifting, but only when the throttle is partially closed, not all the way... like 10%. And gas mileage has been better.

it matters more if it is a closed loop system.

My guess is the O2, but any 1/2 decent Mechanic would have a Snap on/OTC diag. computer that can find out if your O2 sensor is dead.

You can also plug a volt meter to the O2 wires and see if they cycle or even give a reading.

Could be your ecu, I had a galant that had the same problem, is there visible smoke at idle? Mine would run , very rich but it would drive and use tonnes of fuel , if it is anything but a 89 you can put a datalogger on it. If so you can see the sensor voltages are all at 5v or so, which means bad ecu. Worth a shot