Si lo haces desde el móvil con rootexploter,te metes en system/ app/y la apk en cuestión es secphone,y el icono suele estar en la carpeta drawavle-xhdpi,con el nombre de icon.png o parecido,te recomiendo que le des a extraer a la apk,y una vez descomprimido vas viendo las distintas carpetas e iconos,desde el pc ídem de lo mismo,descomprime la apk y así ves visualmente el icono a cambiar
La plantilla es esa misma que has mencionado
