from your description of your problem,it sounds to me,it's in your fuel circuit,have you tested injector circuit from ECU to injectors? fuel pump....can you hear it when you turn the ignition on?
people say that the O2 sensor effects your fuel consumption,this is arguable,it's an emission control type device really,in theory why would the O2 sensor be placed on the exhaust for the waste gases,where does the fuel consumption come into it with exhaust waste?the only way this could happen is if raw fuel was escaping.