[bitozoid]

No lo he probado demasiado pero a mí me parece que rula. Te lo detallo por pasos.

2. Te creas un directorio de trabajo. Al mío lo he llamado 'apps'. Mira que soy original.
3. Dentro te creas dos subdirectorios: 'pre' y 'post'. En 'pre' metes todos tus apks sin renombrar.
4. Te bajas el SDK de Android y con él el 'SDK Platform Android 2.2', que trae la herramienta aapt.
5. En el directorio de trabajo, creas este script. Yo lo he llamado rename_apk.sh:

#!/bin/bash

TARGETDIR=/home/bitozoid/Desktop/apps
TARGETPRE="$TARGETDIR/pre"
TARGETPOST="$TARGETDIR/post"
AAPT=/home/bitozoid/Desktop/android-sdk-linux_86/platforms/android-8/tools/aapt

pushd "$TARGETPRE"

for i in *.apk; do
    echo Procesando "$i"...
    name=`$AAPT d xmltree "$i" AndroidManifest.xml | grep "package=" | head -1 | cut -d'"' -f 2`
    echo "   Nombre:" $name
    version=`$AAPT d xmltree "$i" AndroidManifest.xml | grep versionName | head -1 | cut -d'"' -f 2`
    echo "   Version:" $version
    mv -v "$i" "$TARGETPOST/$name-$version-${i/\.apk/}.apk"
done

6. Modificas las variables de entorno del script, editándolo directamente en el fichero. En particular, modifica TARGETDIR y AAPT.
7. Ejecuta el script. Debes darle permisos de ejecución primero. Desde el directorio de trabajo y con una terminal, lo puedes hacer con

$ chmod +x rename_apk.sh
$ ./rename_apk.sh

Ya está.

PD: Olvidé el primer paso:
1. Instálate un GNU/Linux. Mejor Gentoo. Quizá consigas hacer que rule en Windows con msys. No lo he probado.