I've been collecting data about my headaches and diet for almost four months now. I don't see any patterns - annoyingly, I get headaches nearly every day, so there's not much information - but I thought I'd post the data set and see if anyone sees anything. Here it is. Hopefully someone finds this an interesting problem.
It's written in note-to-self format (abbreviations like "strawbs" for "strawberries"; if I mention a complicated dish once then I'll shorten it when I eat the leftovers, as "pasta" for "pasta with artichokes and spinach and pesto"; times given approximately and not in a consistent form and often without specifying if they're a.m. or p.m., though they are in chronological order). Quantities aren't given, although if they're suspected to be relevant I may be able to remember specific instances (for unusual foods) or typical portions (for ordinary foods) - other details might also be recollectable similarly. I also don't notice when headaches go away, so I don't know how long they last except when they last all day or become noticeably worse during their course. My sleep schedule varied considerably over this period, but trends more night owl than early bird (for a while I was outright nocturnal). I moved three time zones west at the end of July, should that matter at all.
I'm not soliciting commentary on my diet except insofar as it can be compellingly related to my headaches.
ETA: Assume that every single day I'm drinking lots of skim milk. (2-6 cups depending on how much I eat and how it's spaced out.) There's a couple of exceptions, mostly when I'm in transit for most of a day or run out of milk, but not many and they don't seem to correlate with headaches.
I think you're on the right track with diet - headaches on a semiregular daily schedule sounds a lot like consumption of food on a semiregular daily schedule. Nothing in the data set jumped out at me straight away, so I expect it will be a hard-to-find dietary problem. "All your life" suggests a widely available property, such that its presence is invariant over changes in location and diet.
Ctrl-f "no headache" didn't help much.
Based on this line of reasoning, I suspect a mild gluten intolerance. The only test I'm aware of is rather expensive: buying gluten-free bread, and avoiding cereal and pasta for two-ish weeks.
Searching for what giving up gluten is like regarding headaches: gluten withdrawal is apparently a thing (see the July entry), so if gluten-free makes the headaches worse, it's one of those arduous treks through low-utility space to get from under a local optimum.
I'd recommend more research on gluten-free to be sure of details.
I don't think going gluten-free has to be expensive if you don't go for gluten-free products which resemble foods that would normally have gluten. On the other hand, you do have to take complete control of what you're eating. For example, most soy sauce has gluten in it.
Alicorn, this is a tentative suggestion, as in it might be worth the aggravation but I'm not sure. Have you posted a detailed description of your headaches?