The best example is workbench.developerforce.com. When you first try to login with it Salesforce asks for allowing access fro your application (if you are not logged in into your org, then login + password, and only then Allow/Deny). I want to do the same. But every option (https://developer.salesforce.com/docs/atlas.en-us.api_rest.meta/api_rest/intro_understanding_authentication.htm) I found requires either Connected App to be created prior connection or some other credentials (client_id, secret), which my application won't know.
You don't have to create a new connected app for every org your app will connect with.
You create a connected app only once and then use same client id and secret everywhere.
When you authorize that app first then it gets its entry in the connected app section.
What you are looking for is the Webser Oauth flow of salesforce where Server can securly store the secret.