Ah, just thought of something. Your phone is stock. If so, you do have Twidroyd on it. It's preinstalled bloatware. The app has since merged with another Twitter client and changed its name to UberSocial, but it's still Twidroyd on your phone. That's where the push ads are coming from.
Here's what you can do for now, without rooting. Go into manage apps, click on Twidroyd, and uninstall updates and data. Make sure you are not logged into the app at all (probably easy enough if you don't use Twitter). Basically, after this, Twidroyd will likely just sit there as an unused app. It probably won't do much. Of course you will still see it in your update menu whenever you go into Google Play, but just remember not to update it. I think that's the only thing you really can do, and hope it works.
The best bet altogether, once you get used to your phone and comfortable with it, is to root. First thing you can do after that is uninstall the pre-installed bloatware. There's a list of apps you can delete somewhere here. Just don't uninstall any Google apps, just to be safe.
