Speaking of giving it a full charge/discharge, are you using, at minimum, the OEM charger? I have an Anker charger that will do either 1.5a/2.1a, and while it does its job fine, I noticed two things having chargers to compare. More than these two (OEM and Anker).
First, the Anker aftermarket charger does not act like the Samsung does when you reach full charge. The Samsung cuts back or off, I do not have the technical data behind it, so forgive this poor description, but again, the Samsung model on a fully charged Samsung S3 goes into some mode that keeps the phone at 100% over night while not having to activate a "near full" charging mode again.
The Anker charger seems to fully cut off, allowing the phone to discharge, and then the phone will beep and indicate it is charging again. It will do this every 10-15 minutes, infinitely, until unplugged. I didn't know this, at first, and it completely killed my battery life. It showed that it drained three times as fast. I thought it had ruined my battery, but going back to the OEM charger sorted it out after about 4 days later.
Wow, accidentally deleted a lot about 28/24 AWG USB cables. Damn you, android, I need a ctrl+z equivalent. In the end, I was just trying to throw out some ideas that can help eliminate some baseline problems.