Do you use 有 if you speak about 头疼?
I'm wondering why there's 会 used here.

会 in here mean always. I'm always getting headaches.

Would this sentence be correct? 我常常头疼

Yes, it is correct

Would this sentence be correct? 我头疼

Yes, it is correct

So would this sentence be correct? 我有头疼

Incorrect. You can't use 有 in this sentences. If you want to use it, the correct should be 我刚刚有头疼