REST API without Connected App

Definitely doable. The admin should not have to customize anything:

1. create your Connected App, once, in an org with a managed package and namespace,
2. bake that exact client_id into the runtime code that you distribute,
3. use Web Server authentication flow or Username-Password flow when calling REST API,

Maybe there is a misunderstanding of how Connected App really operates here. Imagine a Salesforce Package as an analogy. You control the true source code in a Packaging / Release Org but you deploy or install a special instance of it. Similarly with a Connected App:

• you control the Connected App 'definition' including client_id and secret,
• a user allows (or a sysadmin can manage) the connected app 'instance' when it's used.

Does this help?

@bigassforce's answer is correct in that you don't need separate connected apps for each org.

As per metadaddy's comments, for an external app the OAuth 2.0 User-Agent Flow is more secure with Salesforce handling the username and password input and the secret not being embedded in the application that is distributed to the client.

From the docs (my emphasis):

[For applications] implemented in a browser using a scripting language such as JavaScript, or from a mobile device or a desktop application. These consumers cannot keep the client secret confidential. The authentication of the consumer is based on the user-agent's same-origin policy.

...

This user-agent authentication flow doesn't utilize the client secret since the client executables reside on the end-user's computer or device, which makes the client secret accessible and exploitable.

---

Generally speaking, don't do the following unless someone has a gun to your head. It's much better all round for everyone if the user never directly gives you their credentials.

That said, there are alternatives available, such as the OAuth 2.0 Username-Password Flow. Once you have collected the username and password+securitytoken you can use the password grant_type to get an access token.

Also note that the access token is generally interchangeable with a session id (depending on the scope requested). You could also get the session id from the SOAP API login methods, composite apps, or even from a browsers Salesforce sid cookie.