Hola!
Lo primero que haría sería quitar los datos, incluso ponerlo en modo avión por si no sólo te está poniendo publicidad si no que además se está metiendo en más sitios como tus contactos, notas, etc. y los manda a su servidor para hackearte o borrarte cosas...
Lo siguiente que haría sería ir a desinstalar todos aquellos programas que has instalado últimamente.
En ajustes puedes ver los programas que se están ejecutando en ese momento, mira a ver si ves alguno extraño.
También iría a ajustes / uso de datos, para ver si hay alguna aplicación que te está consumiendo.
Después de hacer estos pasos, vuelve a activar el internet y mira a ver si sigue la publi