You've not stated which browser you're using. If you're not already using Firefox, give it a try because it's extremely effective at blocking pop-ups generated by websites. (Chrome probably does the same, but I've not tried it myself).
However, since you seem to have tried some of the usual solutions for blocking pop-ups, I wonder whether you're actually seeing messages generated by malware rather than true 'pop-ups'?
If you only get pop-up windows opening when you visit specific websites, then you're seeing 'genuine' pop-ups, generated by those sites. However, if you receive messages irrespective of the site you're visiting (or even whether you're actually online), such as the ones that ask you to click on them to to remove malware , then they're not 'true' pop-ups. You could have a hundred pop-up blockers installed and they'd still appear.
If your 'pop-ups' are actually generated by malware, you should try running a full virus scan, plus searching for the cause of the problem with programs like Adaware and Spybot.
Chris