El Adblock plus funciona también con los datos, sólo hay que ponerle la misma configuración que en la red wifi. El problema es que tarda más en cargar las páginas y tal, en los foros oficiales hay más información sobre ello
Como han dicho también esta Firefox y Dolphin con las extensiones, yo uso el primero y de momento bastante bien. Luego, aunque no tiene nada que ver con los navegadores, existe Lucky Patcher con el que se puede quitar la publicidad de las aplicaciones.
Todo esto sin ser root.