Is there anything in the notification window when these ads popup? Do you have a screen shot?
I ask because there seems to be two different kinds of ads: those who have a notification and those who don't. With the first kind, you can just do what you said and kill the app's notifications. If it's the second kind, you will have to uninstall anything that may be causing it until it goes away.
My wife used my old S3 for a while and was plagued by this problem. I had never seen it before, but she had a few shopping apps that I don't use.
Sent from my GS5