OK all problems fixed!
The origin of the problems was that I had installed Python App Engine 2.7 before all of this, and trying to migrate to App Engine 3.7.
The problem was that "/usr/lib/google-cloud-sdk/platform/google_appengine" was in my PYTHONPATH. Probably because this directory contains a "google" subdirectory, but no "type" subdirectory inside "google". I'm not sure if this was the problem... What I did that fixed this was i ran "sudo apt remove google-cloud-sdk" and then installed again the latest SDK with "sudo apt-get update && sudo apt-get install google-cloud-sdk", which didn't create this folder again. It created "/usr/lib/google-cloud-sdk/platform/" but with no "google_appengine" inside it. Also I should have a look at how to remove that dir from my PYTHONPATH as it doesn't exist any more.
After all this I just had to create an authentication and setting "export GOOGLE_APPLICATION_CREDENTIALS="pah to file.json", and then "python main.py" started the application using python 3.6 interpreter.
Thanks!