Welcome to the forum!

Hmm. Hard to believe that there was no cat on the car - that would have been the first code stored or one of the codes stored with the P1656 code.

Who verified that - the mechanic or you? The cat is underneath the car, almost between the front edge of the front two seats. If it is truely gone, I would get a hold of the person you got it from. Unless they explicitly told you it was removed - you cannot legally register the vehicle for street use in most areas.

The car uses a specific three-way catalytic converter. The universal ones are great for older cars, but the newer ones will pop up a CEL if they are not attached to the correct type. Doesn't mean you cannot use an aftermarket one - as long as it is a 3-way converter - you should be OK. Unfortunantly, most 3-way converters that will fit in that location are pretty expensive.

You should replace the O2 sensors will OEM like sensors - that way you will not have to worry about the number of wires. If you're wondering - the upstream (pre-cat) O2 sensor is a 2-wire, the downstream (post-cat)O2 sensor is a 4-wire unit - usually the front O2 sensor is cheaper than the rear O2 sensor, because the rear one has a built in heater element. Same way with the catalytic converter - they make OEM direct fit and universal. The universal ones might be more attractive, price wise, but you will have to cannibalize the original connectors from the old O2 sensors and solder them on the new sensors. Wire them incorrectly or poorly, and you'll get an impedance mismatch issue and a CEL - not worth the hassle, spend the extra couple of bucks and get the good ones.

As long as the O2 sensors and engine are running within spec - you shouldn't have a problem with the new cat. I'm concerned about the P1656 code - usually a simple fix (loose connector) or expensive fix (replace ECM or Oil Control Valve - part of the VVT-i system). I would also monitor the oil consumption of the engine - if it starts to burn a lot of oil or your oil drains look bad - I would dump the car. Most of the time when you see a OCV issue, it is usually due to poor maintenance on the part of the previous owner, though, every once and a while a lemon will make it past QC. It wouldn't hurt to send in a oil sample to be analyzed. Could tell you if you keep or dump the car.

Running without the cat will not hurt the car at all. Most of the feedback information is from the upstream O2 sensor (readings before it even hits the cat). Some people prefer not to run with a cat, if they are allowed to - they make dummy sensor loads o trick the ECM in thinking that the rear O2 sensor readings are fine (tricks the computer into thinking that the cat is there, even when it is not).

I would run one regular oil change through the engine to make sure any assembly instroduced contaminants are reduced and then take an oil sample at the second oil change. Most people pull their sample when they drain the oil - just easier to do then.

As for the poor fuel economy - harder to say. Usually a bad O2 sensor will cause the fuel economy to drop that much. Running without a cat also tends to pull the fuel economy down a bit (freer flowing exhaust), but not into those levels. I would check the obvious things first - missing or damaged vacuum lines, cooling system issues, ignition issues, fuel system issues, and emissions. About 90% of the problems will be run down by visual inspections. Running on LPG shouldn't hurt - as most cars can do it with only slight modifications - but normal routines should also be followed. There are probably a few hundred thousand LP powered vehicles in the US - most are under the impression that the fuel burns so clean, that you can extend the normal maintenance schedules - this is where most of the problems come from. But Toyotas are pretty tough - a little more time and regular maintenance - you should be running well in no time. Good Luck.