want to push/pull data into/from SalesForce Accounts/leads from/to my external web app
You're mixing up a couple of independent issues here.

If you're going to authenticate via OAuth, you must have a Connected App. 
A SOAP API login() call requires you to store a username and password, which is undesirable.
There is no way to "permanently" authenticate, i.e., to get a session id that never expires. Your app must always be ready to get a new access token via the OAuth refresh token it obtains and stores (via, for example, the Web Server OAuth flow), or to reauthenticate via JWT flow.
Connected Apps are global metadata in most cases. You don't need to deploy a Connected App into a target org in order to authenticate using its Client Id and Secret into that org. The only exception I'm aware of is if you want to use the JWT flow with a certificate and preauthorized Profiles and Permission Sets.
Based on what you've shared, I don't see any reason for the AppExchange to be involved.
I have my web application. Now i want to integrate salesforce into my web app so that i can push data from my app to any salesforce org after the authentication(OAuth).
I found 2 ways:
1. Connected Apps
2. via wsdl generation file and use
I created a connected app from my developer account and i authenticated using consumer key, cusumer secret key(from my connected app) and username of user and secret token of the user account.
I tried with another free trail account, It's validating and fetching the details and post data also working.
My question is, shall i deploy my connected app into app exchange, then only i caan use REST APIs ?

generating wsdl and coding around is the better option than the above ?

Is there a option, only one time authentication enough for any number of sessions and use the REST APIs?
Please suggest me a best way to proceed.