How to prevent arbitrary client apps from using anonymous web API?
Solution 1:
You can't prevent people from copying your client code or replaying network traffic.
Thanks to the same origin policy, other web apps can't access your API from the client. They will have to proxy their requests via the server, meaning these requests will come from a handful of easily identified IP addresses, which you can temporarily blacklist.
As for desktop and mobile apps, there's not much you can do. My advice is to not worry about them until they're a problem.
That said, it doesn't hurt to be prepared. If you want to avoid expensive legal battles, one thing you can do is change your API method signatures from time to time. Leaching apps can be fixed, but their reputation will steadily decline.
Solution 2:
Authentication doesn't prevent abuse of your API's either. As long as the client can correctly authenticate with your system, he can use any client he / she chooses. Only the case where the client and the server are both secure and the connection is secure can you avoid abuse.
If the problem is abuse, then a simple throttling solution may be adequate.
Solution 3:
If your client has code that is hidden from snoopers, could you not do as you suggested, use salts, ip address and time based values, encrypt them and then do the same on the server end? This is basically what mod_auth_tkt does, and it works well. Or would that constitute authentication?