I encountered this problem today in Godot 3.4.2. Like you, I tried experimented with changing several paths, installing new versions of build_tools and upgrading my JDK. The following finally fixed my issue:
Uninstall OpenJDK 11 (and OpenJDK 8, if you have it)
Uninstall Android Studio
Delete all files from %USER_HOME%\appdata\Local\Android\Sdk
Reinstall OpenJDK 11
Install the Android SDK using the command line tools described in Godot’s instructions: sdkmanager --sdk_root=<android_sdk_path> "platform-tools" "build-tools;30.0.3" "platforms;android-29" "cmdline-tools;latest" "cmake;3.10.2.4988404" "ndk;21.4.7075529"
I think the most crucial step is deleting the files from %USER_HOME%\appdata\Local\Android\Sdk. indicate that the apksigner fails if you have older build-tools versions installed.
Thank You! Simply deleting the Sdk folder that you mentioned and reinstalling it fixed the issue for me!
LyguN | 2022-01-03 22:39
Thank You! It helped me as well. I was about to give up. Now it finally works.