A bad cat will make the performace of the truck real bad (no power while driving, idle bad ect.). You would be going through alot of gas too. Maybe try to clean the mass air flow sensor. The mass air flow sensor regulates the amount of air fuel mixture. I know when I cleaned the mass air flow sensor and changed the o2 sensor my gas milage increased. How did the plugs look when you changed them. Did they look like the truck was running rich? They should look tan. I was told to use denso factory plugs due to the double prong for the electrode. When my starter was going in would not turn over like a dead spot when trying to start the truck.