If the catalytic convertor is truly plugged, you wouldn't be able to drive the vehicle, so this makes me wonder about the veracity of your statement. With a plugged cat, the back pressure created behind it will only let you rev the engine to around 1500-2000 rpm. I had to replace a set of heads on a pick-up truck for a guy because he continued to run the vehicle after the cat went bad. He drove it by keeping the gas pedal floored all the time. This cracked the head at the combustion chamber, which allowed coolant to leak into the cylinder. I gave the original diagnosis as a blown head gasket. This was before I tore it apart, found the cracked head, then discovered the cat was plugged, which was the original problem. This is a definite probability for any vehicle which gets run in the same manner.
Gas mileage will definitely be affected because you have to run the engine harder to overcome the back pressure.
You can take the convertors out and put in straight pipe. If this is an OBD-II system (which I assume it is because from your description it has "cats" and O2 sensors), you will never get the light off your dash without reprogramming your computer or installing O2 sims. In any state (or country) with emissions testing, this will fail. Better to just get new cats put in. If you don't have emissions testing and don't mind the dash light, there wouldn't be an issue with running it that way. You would, however, never know if there was another issue which popped up with the vehicle. This is a "do at your own risk" type of deal.