As I mentioned above, the problem is that zip doesn’t create intermediate directories. If you run it like this zip build/libs/whatever.zip whatever.zip it won’t create libs directory, but will spit an error. I did it manually and it worked for me.
Maybe, Gradle has it’s own implementation of zip somewhere, and I did install one from my system repos, and mine doesn’t create directories if they don’t exist (or it needs a specific flag to do so).
I tried manually removing build and then running ./gradlew build: it yields the same error. Again, manually created libs directory solves this problem.