¿Cómo renombrar archivos por lotes?

Esto es ciertamente posible con tasker, aunque no puedo darte la "receta completa". Básicamente, podrías crear una tarea como esta:

• Ejecutar Comando: ls -1 /ruta/a/tus/archivos, y capturar la salida en una variable
  el comando mostrará todos los archivos en el directorio especificado, uno por línea
• Trabajar en la variable. Hay posibilidades de convertirla en un arreglo, de modo que puedas usar un bucle for para manejar cada archivo
• de nuevo con variables, puedes configurar el comando de renombrar (por ejemplo, usando Variable Search Replace) en una nueva variable. Pseudo-Código: mv "$nombre_antiguo" "$(s/ /_/,$nombre_antiguo)"

Pero es mucho más fácil usar un simple script de shell en alguna aplicación de terminal (o a través de adb shell) para lograr lo mismo:

cd /ruta/a/tus/archivos
for archivo in $(ls -1); do mv "$archivo" "$(echo $archivo|sed 's/ /_/g')"; done