How workbench is able to log into Salesforce with OAuth
Connected apps only need to be defined one total, not once per org. You can use any org, like a free developer org, to set up the oAuth/connected app info, and then use that with as many consumer orgs as you want.
It's kind of old post but i felt very motivated to provide some more information regarding Workbench here.
The first thing is you can actually package the connected apps so that you don't need to create them every time on every org. You just need to install them there.
In case of workbench actually Salesforce installs a package through automated process. For more information about this package you can see my answer in this thread
This package is generally pre installed or get installed when you access workbench first time.