I have an allergy to the histamines in various aged cheeses such as parmesan, romano, blue cheeses, etc.
Many recipes call for parmesan for saltiness and flavor. What possible substitutes are there for these flavours?
Based on the information you've given, it sounds like what you're describing is not technically an allergy but histamine intolerance. In an allergic reaction, histamines are produced by the body as part of an immune reaction. Histamine intolerance is due to an underproduction of the enzyme that normally breaks down histamine. This means that foods that naturally contain histamines (such as aged cheeses) are poorly tolerated.1
Histamine Intolerance If your problem truly is histamine intolerance, then there is not much that I can suggest. Any aged cheese, cow's milk or not, will contain histamines as well as many non-dairy cheese substitutes (such as soy cheese).2 Fresh cheeses -- ricotta, cottage cheese, queso fresco, etc. -- should be safe,3 however, they will not provide the same flavour and texture as Parmesan.
Since the exact degree of histamine intolerance varies from person-to-person, it is possible that you might tolerate some cheeses or cheese-substitutes better than others. Younger cheeses should have lower levels of histamines than older cheeses. Antihistamines may also be able to help you cope with histamine-containing foods. (Much the way that people with lactose intolerance can take lactase pills to help them digest lactose-containing foods.) I would strongly recommend consulting with your doctor before trying any new foods, especially if you are prone to particularly strong reactions.
Allergy If your problem actually is an allergy, then which substitutes are appropriate will depend on exactly which component of the cheese you are allergic too. The most common "cheese allergies" are protein allergies to either casein or whey protein1. If you are allergic to one or both of these proteins, then it is unlikely that any dairy product will be a safe substitute. However, it is possible in this case that non-dairy soy cheeses or similar would be perfectly fine to use.
Some cheese allergies, however, are specific to certain types of milk and some people who are unable to tolerate cow's milk products are able to digest sheep or goat's milk products. Again, I would recommend consulting your doctor before experimenting with any dietary changes.
Information compiled from several online sources as well as my own experience as a cheese-maker.