Summary: I would just take the risk and keep the secret in the client app.
Proxy server alternative:
The only way you can reasonable mitigate the problems I list below and make the proxy-ing work, would be to go the whole nine yards - move all the business logic for dealing with the resources on the third party webservice to your proxy server, and make the client app dumb terminal with rich UI. This way, the only actions the malicious app would be able to make the proxy perform on its behalf would be only what your business logic legitimately needs.
But now you get in the realm of a whole slew of other problems having to deal with reliability and scalability.
Long deliberation on why simple proxy wouldn't work:
Some people, when confronted with a
problem, think “I know, I'll add my
own proxy server” Now they have two
problems. (with apologies to Jamie
Zawinski)
Your assumptions are largely right. Right down to the point where you start thinking about your own server, whether it keeps the secret and proxies the calls for the client app, or it attempts to determine if the app is legitimate and give it the secret. In both approaches, you still have to solve the problem of "is this request coming from a piece of code I wrote"?
Let me repeat - there is no way to distinguish on the wire that particular piece of software is running. If the data in the messages looks right, nothing can prove it's another app that's sending that message.
At the end of the day, if I am writing a malicious app, I don't care if I actually know the real secret, as long as I can make somebody that knows it do a work on my behalf. So, if you think a malicious app can impersonate your app to the third party OAuth servers, why are you certain it can't impersonate your app to your proxy?
But wait, there's more. The domain at which your proxy service is located, is your identity to both your clients and the OAuth provider (as shown to the end user by the OAuth provider). If a malicious app can make your server do bad stuff, not only is your key revoked, but your public web identity is also not trusted anymore.
I will start with the obvious - there is no way to distinguish on the wire that particular piece of software is running. If the data in the messages looks right, nothing can prove it's another app that's sending that message.
Thus, any algorithm that relies on app-side stored secret can be spoofed. OAuth's strength is that it never gives the user's credentials to the app, instead giving the app temporary credentials of it's own that the user can revoke if necessary.
Of course, the weak point here is that a sufficiently good app can get the user to trust it and not revoke the credentials, before it finished its nefarious deeds.
However, one way to mitigate this is Google's approach of using 3-legged OAuth, instead of the standard 2-legged. In the 3-legged OAuth, there's no pre-assigned secret, but on every authentication a new access token secret is issued, along with each access token. While ultimately this suffers from the same drawback, as a bad app can read the good app's token secret from its process, it does result in the user having to approve the app access every time it needs new access token.
And of course, this also means that it's a bit more inconvenient and annoying for the user.