My thoughts: see the ENT.

It's normal for your breathing to switch from nostril to nostril; it's usually a three-hour cycle, and if one side is partially blocked because of congestion or inflammation (possibly in combination with a deviated septum; no one's sinuses are exactly the same on both sides), it can become completely blocked when the turbinates swell to switch to the other side.

It's odd that you can identify some definite allergies (hay fever, cashews, skin reactions to various things), and that an antihistamine helped, but that you tested negative when you were tested. Did they do the intracutaneous titration, or just single dilution pricks? Do you know what they tested you for? Might want to either see a different allergist, or choose an ENT who has an allergy practice.

IANAD, etc., etc....