I still use AdAway (with only the MVPS blocking hosts file - updated once a month) on both my rooted Note 2 and OG Note 10.1 (both still on Jelly Bean) and never see ads. But haven't been able to use it yet on the Note 4 since my Verizon retail version still doesn't have root access yet. It should work on a rooted Note 4 with Kit Kat though as long as the app is able to modify the system hosts file (which has all the entries to block most known ad networks).
You can get AdAway directly from the dev here:
https://sufficientlysecure.org/index.php/adaway/ since Google has banned ad blocking apps like that from the Playstore a while ago.
Also, if you're using the Chrome browser with the "Reduce data usage" setting enabled (Settings > Bandwidth Management > Reduce data usage), you'll probably still see ads because it forces info to go through Google's servers.