Well, you are not going to believe this... I had the same issue with my S4 Wifi connectivity as most everyone here and got an idea from one of the posts that I read, after trying virtually everything else.
I have two replacement batteries, but I had starting using the original Samsung battery when the trouble started. I switched to one of the after market replacement batteries (available on Ebay, for example, for like $3 - 4 dollars,) and that was all there was to it!! Problem solved.
I will leave it to one of you that know more about this than I do to explain why, but trust me, it worked!