Ok, here is the thing - I have two phones that had same simptoms. First is prestigio psp 3404 duo, android v4.4.2 and second is NOA c25 (which seems to be croatian name for chinese servier h18), android v5.0.
It looks like I was able to clean NOA by turning on airplane mode, than rebooting into safe mode and doing factory reset. No popus for several days since then.
On the other hand, prestigio still shows popups occasionaly (even after factory reset). I tried to identify app that causes problems and positvely pinpointed ProxyServer as a source of notifications in notification toolbar. Disabling notifications from ProxyServer prevnted further notifications to be displayed.
However, full screen popups still show up from time to time (frequency being increased by time from last factory reset and frequency of the use - I was able to get it run without ads for half a day or more).
I disabled all apps that were installed and disabled preinstalled apps. Also disabled most of the system apps. Tricky part is that looking at the recent apps doesn't show one that shows ads (seems like it closes itself as soon as it looses focus).
For the NOA, I can pinpoint moment when ads atarted showing app and this is when I installed CM lite and 360 security. For prestigio I don't know when problem started and what caused it and don't know how owner tried to clean it, so it was exposed for the longer period of time.
Any suggestions what to do next?