Mine does not produce black smoke on accel, that's not normal. It didn't when I had no cat either. However, my tips do have black soot on them on the inside and on the lip. That is pretty normal.
Like I said though, you need to check your front one, its the one that controls the A/F ratio, not the rear. Sim'ng the rear isn't going to help that, it will get rid of a check engine light for poor catalytic efficiency though.
Other things to check would be your plugs and wires if you haven't done a tune up in a while that might be in order as well. However, I still lean towards the front O2 sensor giving a misleading signal to the PCM causing a slight rich mixture. That wouldn't throw a code, wheras a signal thats WAY off would.