Have you checked the resistance on the #4 wire? I had a car in the shop the other day that had new plugs & wires, however the ceramic on one of the plugs was cracked and caused the plug to fire to ground instead of the combustion chamber. Without seeing the plug or knowing the age and condition of the engine, I assumed by your description of the "black tar-like deposits" that either it was oil, or the plug has not fired in quite some time. One dead cylinder can cause a “rough idle that turns into a full miss at speed”. Never assume that a new part is flawless!!
Move the #4 plug to another cylinder and see if it burns clean after it is relocated. (That is, if you don't have a new one to try on #4).