"会" in the sentence is an 助动词 (auxiliary verb), which means 表示有可能实现 (be possible to achieve). See the definition in 百度百科。例子:如果你考试题都会(known well)做,你就不会(possible to)头疼。
As you see, 会 implies uncertainty. So that see the following:
我头疼。Yes, you have headache, right now. By the way, this is actually 我(的)头疼 with 的 omitted.
我常常头疼。Yes, you have headache, always. By the way, this is actually 我常常(感到)头疼 with 感到 omitted.
我常常会头疼。This one is almost interchangeable with the previous one, but not as confident, because there is an implication of possibility. For example, "Dad, 我头疼,不想写作业了",or "Doctor, 我常常头疼,给我开药", or "Whenever I saw the face of Mr. Trump, 我就常常会感到头疼"。You see the difference? Because of the possibility, it is often used with other word implicating uncertainty. For example, 我的头常常会感到有些/若有似无的/莫名其妙的疼。It is pretty intuitive to compare "会" and "不会" with possible and impossible.
我有头疼 is awkwardly correct in grammar if you consider 头疼 as headache which is a noun. However, Chinese has some set structures, "头疼" is not something you can "有"。You should say you "感到头疼", or you 有/患有 some "病/症/疾" instead. You can say, 我感到头疼/头晕/头胀,我有头疼的毛病,我有头痛之疾,我有痴呆症。Without the 感到 or 病/症/疾, those are not Chinese convention, though still understandable.