I used to share a small room with two other coworkers, one of which had this annoying habit of repeatedly shaking his leg up and down (even while not listening to music), to the point where the noise was really irritating and distracting.

My solution was to simply politely ask my coworker to refrain from doing this. After I informed him of this, he would stop shaking his leg so much, but still occasionally did it anyways (it must have been habitual, after all). So when it continued, I simply tried to do my best to ignore it (sometimes my work was so interesting and engrossing that this was easy). Other times, when I simply couldn't focus, I would politely point out to my coworker that he was shaking his leg again, at which point he would stop again (at least for a few hours, or the day).

If you work in a larger office, or otherwise have the option of moving to another location that's far enough away that you won't be distracted by your coworker, I would consider that an option.

I could see that some people might suggest escalating the issue to a supervisor if your coworker won't listen when you inform him that the leg shaking is distracting. It's definitely an option, but it's only one that I would take as a last resort. I would much prefer to just find another location in the office to work, personally.