Is it possible to upload a template file to a directory that can be used by all themes?

No, WordPress has no default place in its system where it will look for templates outside the current theme folder.

That said, you can easily build a plugin that inserts a template into the system. You can use the theme_page_templates to insert a template name in the dropdown list. Then you hook into template_include and depending on whether get_page_template_slug return your template’s slug you divert the template to the one in your plugin-directory.