You need to learn to stand up for yourself and to stop letting things like unpleasant co-workers bother you. Most jobs have someone unpleasant. Just about every job has gossips. Right now you are acting and thinking like a victim, you need to learn to be more assertive. There are plenty of books on this and I suggest you read some of them (and a couple of books on office politics would help tremendously too). I was very shy when I started working too. But shyness is one thing you can't afford in the workplace and not standing up for yourself is another. You will always find the workplace difficult until you learn to stand up for yourself.
Another thing to keep in mind is this is an unpleasant person. He is not out to get you specifically. So don't take things so personally. Instead think, "It must be sad for him to be so unhappy that he has to act that way." He may also have personal problem you know nothing about that are causing him stress and it is coming out in obnoxious behavior. Ask yourself if you would let the behavior go if you knew that his son was dying of cancer for instance. Sometimes it helps to assume that something is wrong in his life and just let it go.
Sometimes you can turn around someone who is not your best friend at work by complimenting them on something they did do right and ignoring the bad. I had a colleague once who resented that they had even created my job and who thought it was unneeded. It took me a awhile to turn him around but since he felt somewhat threatened by the very existence of my job, I made sure to publically compliment him every chance I got. (He was good at his job and I did need to work closely with him at times.) This serves several purposes, first most people like to be complimented and have a better impression of you if you seem to have a good impression of them. Next it disarms him by making him look like a fool for attacking you when you clearly respect him. Finally, because you took the high road rather than descending to his level, then you look better to the other people in the office.
If gossips are linking you to this man you don't like, then speak up and say something that will divert them to a new topic or let them know you are most definitely not interested. But do it conversationally and perhaps with a laugh about how silly the whole idea even is. I have found that treating something mean as an obvious joke and simply laughing at the suggestion is often more effective than protesting it is not true.
When someone disrespects you publicly, then you need to speak up right at that moment and tell them that the behavior is not appreciated. For instance, in the situation you describe where he asked you to not message him. I would have told him I'm sorry I didn't know you don't like that type of communication and I won't do it again (and keep everything to email from then on). If he said that in an aggressive way, I might have added something to the effect of "However, it was an honest mistake on my part since I did not know, so your tone is unwarranted and unappreciated" and remind him that he needs to treat me professionally. However, if he persisted in making comments about how stupid you were to use messaging, then I would smack him down verbally when he did it by pointing out that he needed to come into the 21st century. If he still persists after you have asked him to stop behaving unprofessionally to you, then you can escalate to HR or your boss with documentation of what specifically was said and when. But don't escalate unless what he did was truly horrendous (and preferably when you have witnesses who will back you up, not always possible I know, but it strengthens your case) and not just ordinary obnoxious behavior.
Don't quit and look for another job, learn to cope. Then you can look for another job knowing that you will be able to handle whatever jerks they have.
