authentication method
Let me just add a few random thoughts/comments to your proposals.

RSA: Since you are mainly interested in authentication, I assume you'd want to use RSA signatures. This would imply that each user needs his own privat key. To me that sounds a little bit like overkill, especially when user and server already share common secrets (i.e., passwords).
Using SHA256 is a good approach. I have some problems to understand why you include a salt, since a salt is commonly use to avoid that an attacker precomputes hashes of dictionaries. To be clear: dicitionary attacks are a problem here. An attacker could try to hash messages with all passwords from a dictionary. Just he has to reapeat this attack for each user and can't reuse precomputed values. One way to make such an attack a little
more difficult is called key strengthening, e.g. by reapeatedly hashing the result n times
and hence forcing an attacker to perform more work during a dictionary attack.
I completely agree that HMAC is better than just SHA-256. After all HMAC was designed for authentication. I'm not sure why you want to hash the message before computing the HMAC. HMAC does that for you.
Encryption does not always provide authentication. This is specially in cases when the attacker learns the plaintext, as he does in your case. He might be able to exploit properties of the encryption mode to manipulate the ciphertext an know exactly how the resulting plaintext will look like (E.g. the CBC mode allows these kind of manipulations). Your previous proposal (HMAC) is preferable.

Finally, if you can setup an SSL connection between user and server, as others suggest: this would be a much safer solution, since not even the dicionary attack mentioned above would be possible.
I am writing a server-client application to receive user message and publish it.
Thinking about authentication method.

Asymmetric encryption,  probably RSA.
Hash (salt+password+'msg'+'userid'), SHA256
HMAC, SHA256. seems to be more secured than the method 2. Also involve hashing the password and msg data.
Symmetric Encryption of the 'msg' with static password stored on both sides, probably AES.

There is no need for encryption as the msg would be publish online anyway. So I am more lean to the HMAC or PKI method.
I'm using java to send the request (including whatever authentication method to be implemented)
www.mysite.com/foo?userid=12345&msg=hello&token=abc1234
python on the server side to receive request and make sure the request is from the valid user.
The problems are in integration and make sure both sides understand each other's authentication token. It is a big factor for me. And the availability of the libraries available on both language are taken into account as well.
Or I can choose to rewrite the server side into java. (Why not python? The client side application need to be in java)
What do you think?

EDIT: I would not treat this as a web application. The application does not serve any webpage. Most of the operations are not related to the web. Just the client-server communication go through internet. And sending POST/GET via HTTP is what I thought of as the simpler albeit insecure way to do it. Feel free to suggest me any other alternative. 
SSL is a secure way for encryption. But it does not prevent attacker from sending message to the server impose as the user. Anyone can initiate a HTTPS connection. And the content of the communication does not need to be encrypted. It will be published online by the server anyway. What I need is a way to authenticate the message and sender.
For now I am lean to HMAC algorithm. RSA would be more secure but it comes with more developer efforts as well. Will see how it goes.
Thank you.