You have to go with the first option (stating that the "username or password is invalid"), and this has nothing to do with security.
Let's say that I usually use JohnGB as my username, but on your service someone else has that username, so I use JohnGB123 instead. Say I've then forgotten my username and I enter JohnGB as my username, but use my correct password.
Is that a correct password and incorrect username or a correct username and an incorrect password?
There is no such thing as having a correct username without its matching password, and no correct password without its matching username. Usernames and passwords only represent anything when used in combination.
Edit: If the username doesn't exist then of course you should consider letting the person know that. You may run up against privacy laws if you do the same thing with an email address though, so you should be careful.