With the exception of losing weight (already a 22 BMI) I tried pretty all of this to no avail. Turns out I had a deviated septum and surgery fixed the problem. As a bonus, I can easily breathe through my nose now.
I've read horror stories about that. Apparently a lot of the problems could be solved by teaching kids how to breathe (no mouth breathing), having a proper diet (chewing), &c. of course once you're fucked you're fucked and you have to go to these extremes to get your life back. It's like our lifestyle is slowly evolving us out of this planet
For comparison, I used some of those nasal strips before surgery and the post-surgery were very comparable, so that might be an inexpensive option to try? I also recall someone mentioning some sort of nose plug thing from Amazon you could get that does the same thing.