TLDR: You need to manually uninstall the app on your debugging device to unblock the Gradle process if you have an app with the same package name but a different signature.

I had the same problem, which kept coming back day after day, without me knowing exactly where it was coming from. I finally identified the problem on my machine, so I'm sharing it here in case of it can help. I'm on Windows with Visual Studio Code for Flutter, and I also often work with Android Studio for native Java development. For me, the problem was VSC's inability to deploy a debug app if another app with the same package name but a different signature is installed on my debug device.

I'm used to how Android Studio works, which in the same situation, displays a clear message saying that the app will be replaced, and asks the user for confirmation. With VSC and Flutter, there is no message or confirmation request, and the Gradle process seems to run indefinitely, without ever displaying an error or telling the user (me) that the app deployment is blocked.

Specific case (or steps to reproduce): I'm currently rewriting an application from Java to Flutter. But I continue to maintain the Java app. At the beginning of the rewrite, I opted to maintain the same package name for both applications. The intention is to try deploying the Flutter app as an update to the existing Java app (I have not yet reached this point, and I am still uncertain of its feasibility).

Anyway, the problem appears when I switch from java to flutter on my debug device. If I need to do some tests on the Java app, while before I was working on Flutter, I have no problem with Android Studio: it detects that my previous build does not match and asks me to confirm uninstallation of the Flutter app to replace it with the Java app. Then, when I need to do the opposite (replace the java app by the flutter app), VSC does not warn me that it has a deployment problem, and I see the Gradle process running indefinitely. The solution here is to manually uninstall the java app, to be able to deploy the flutter app. I suppose, but I haven't tested it, that we could have the same problem if we test an app on the store (with a production signature) and try to go back to the app under development (with a debug signature) without manually uninstalling the production app on the testing device.