Jiayu S3 viruses?

Hello,
I am having through a major problem here. I am trying to figure how got into this and solve this problem.

I am new to android but generally and experienced user. Bought my Jiayu from vickmall about 4 months ago and realised that my phone if infected when random apps where installing themselves from time to time (once very two weeks eg.).
Generally I am installing Google apps only except Adway and a few other essential non google play apps.
Also I am careful with what I installed and most of apps ever download where legit (e.g facebook etc).

Thanks to SDMaid I found a virus SYSTEM app hidden from normal app explorer with the name "Pine" and package name org.slaughter.brilliant. The name itself got me very suspicious. I also noticed that "install from unknown sources" was automatically turned on each time I opening my Wifi or Data.
So I exported the apk and scanned through various online scanner giving me obviously that is harmful.
e.g anubis.iseclab org/?action=result&task_id=18ea3597ad6a61394e5335fefcb c86899&format=html

Un-installed it through SDMaid and then the nightmare came...
I am having numerous of app ads several times a day to the notifications bar or as a shortcut icons that go to google play. I see from time to time a toast says "Downloading" without having any visible result.

You realise that this is not as common as a rogue app can be, besides the fact I am acting like a paranoid at the moment :P....
With SDMaid again through latest modified files I saw 3 files in the ES Explorer folder named "recomm" that had a list with all this spammy apps that I get notifications. I was quite upset and though that ES Explorer (quite known app I think) was packed with rogue apps!?. So I deleted it but nothing. Ads came again the other day.
I tried to see from what app came the ad notification "e.g Holo Launcer" by pressing the notification for a few secs. I saw that it came from trebuchet launcher...

I tried scanning my phone with avg,malwarebytes and kaspersky. I got something only with kaspersky the following file in a .kpsh folder.
virustotal com/en/file/6871be33ba862c4594ffee60444f7cf296cb657e4f1384a27c 1be6a5da0d7078/analysis/

Erased it but it seems to recreate itself again from time to time.

Also scanned trebuchet and settings app here and got these.
virustotal com/en/file/000f796f06f193f2e61eb007d374a06d3211ddb7e1facf3c38 6621e1f024b828/analysis/1442420388/

virustotal com/en/file/bbb2783fb9a2ad9aa94fc71d6b78179917e8669ec266cdd575 8fd1e46f853bdf/analysis/1442420356/

I decided to erase the whole .kpsh folder to see if that solves the problem till now.

My mistake I believe is leaving "Unknown sources" on as it was by default and got to this mess without know what app did all this. I believe that I was going to get a warning before something got installed but unfortunately...no.

I don't know if this was prepacked or something or was totally my mistake somehow but I am slowly giving hope away.
Any suggestion would be very helpful.
Reflash the whole thing is my very very last option since I am not familiar with the process.

Thank you all for the time reading this.