There is an excellent guide on the forums for testing O2 sensors: Testing Your Car O2 Sensor....
Before messing around with the sensors however, it would be a good idea to hook up a cheap OBD2 scanner (ELM 327 + Torque App) and see the values while driving real time; the values to look for are Short Term Fuel Trim, Long Term Fuel Trim, and Ignition Timing, among others. Post the results here if you can, and experienced members can guide you with greater precision.
I have a couple of other questions; is the radiator fan direct or auto, and is the thermostat present and working properly? Is the temperature needle near the middle during normal driving or not?
Also, did you ever get the valve lash clearance (tappets) checked? If yes, what values did the mechanic set it on, and was it done on a stone cold engine?