This same thing pretty much happened to me. Actually exactly the same thing... including the extra Anker batteries and charger as well as testing different cords. I ended up ordering a wireless charging kit, and now all is well. I've been using it with one of the Anker batteries. I ordered the Koolpad charger and the white slim wireless chip off of Amazon. It charges through my Seidio case, and I put velcro onto the charger and the back of the case so that I could easily use it while charging. The wireless charging kit cost about $40 on Amazon (I imagine pretty close to what a new official Sammy charger and cable would cost) and the Koolpad charger came with a black and a white micro USB (not USB 3 but still...) port cover, which I thought was a nice touch.
No guarantee that this would work for you, of course, but it did for me fortunately. If it didn't I would have taken it back to the store (after re-flashing the stock ROM, which may have solved the problem on it's own). Oh yeah, not really sure if this is actually related / possible but I did theorize that the problem may have been kernel related. I had actually been following the wireless charging thread anyways, but if I wasn't already considering spending money on that, the first thing I would have tried would have been a clean install of everything. I was testing out different kernels with Tweaked ROM and the problem started around a new kernel flash, but really can't say if that's related because I was unimpressed with that kernel overall and flashed one that ran better on my phone around the time that the wireless charger showed up (got one day shipping w/ Amazon Prime because shutting down my phone to rotate batteries got old quick, as I'm sure you'll agree). Anyways, good luck. There's lots of good info in that wireless charging thread, if you decide to go that route.