If you want to go down that path we could eventually embed the APK parser in the Dart app?
Otherwise I want to help you. Other devs have definitely been able to publish from Linux. Apktool is a Java jar that has to work everywhere. Are you running Ubuntu? I will try to reproduce and fix all I can