Поснифферив траффик брендированных и небрендированных яндекс карт было установлено что первые ломятся на mobile.maps.yandex.net, а вторые на mobile-partners.maps.yandex.net
Соответственно используя мощь линукса в Android есть два варианта как заставить яндекс.карты быть бесплатными:
через iptables:
iptables -t nat -A OUTPUT -m tcp -p tcp --dport 80 -d 93.158.134.138 -j DNAT --to-destination 93.158.134.156
iptables -t nat -A OUTPUT -m tcp -p tcp --dport 80 -d 213.180.204.138 -j DNAT --to-destination 213.180.204.156
iptables -t nat -A OUTPUT -m tcp -p tcp --dport 80 -d 87.250.250.138 -j DNAT --to-destination 213.180.204.156

через /etc/hosts:
93.158.134.156 mobile.maps.yandex.net
213.180.204.156 mobile.maps.yandex.net


P.S. и да конечно у вас должны быть root права на ваш телефон — он же ваш телефон и вы его хозяин.