iPhone 3GS: Right audio channel broken?
My theory: Obviously, you have tried with several headphones, and the situation has not changed. Your headphone jack might have become dirty.

In some cases, this blocks the connections from one ore more audio channels to the headphone. You might want to try to clean it gently, e.g. with a cotton swab. You can find more info on how to do this here or google a bit. Good luck!

PS: I did overlook the comment on this question, which I virtually duplicated with this answer. Nevertheless, have you tried to fix your iPhone jack with the methods described?