How do libertarians solve issues with contradicting negative rights? Theoretically there can be such issues. E.g. negative right to speak freely vs negative right to have good health. If one says something (right to speak) and other claims that this makes him/her physically sick/shock (i.e. violates right to have good health) and let's suppose it is not just a statement, it is really true (suppose, a doctor proves that) then whose right is more important? Do libertarians grade rights to more and less important in such cases? How can they do that without coercion of one of the participating parties? Or it is ok for libertarian ideology that some issues cannot be solved without coercion and there is no contradiction here?
One thing that must be noted is that the core of libertarian philosophy is Non-aggression principle (NAP).
While it may be a fun political discussion regarding whether speech can harm someone or not (it'd be a tough road to hoe to convince most libertarians of that); if there's a concrete proof of harm of specific speech, then that speech would indeed violate NAP just as much as hitting someone would.
As such, restricting such harmful speech would be in full accordance with libertarian principles.
Please note that libertarianism doesn't have an absolute free speech protection in general - some speech is considered aggression - e.g. verbal and written threats of imminent physical violence (Wikipedia's citation is Murray N. Rothbard, "Self-Defense," ch. 12, in "A Theory of Liberty," pt. 2 of The Ethics of Liberty (New York, N. Y.: New York University Press, 1998; orig. 1982), pp. 77–78, 80. Cf., For a New Liberty, p. 27)
At the very least, if there's a documented proof of speech causing harm, libertarianism allows the one harmed to bring a suit against the harmer. In other words, even if there is no law limiting speech in general, there are ways to address the offense (the best practical example from actual US legal system is the infamous Hogan vs. Gawker lawsuit).
Please note that in this article, Rothbard also discusses what amounts to a general idea asked about (conflict between negative rights).
The general framework to explore such conflict is by ranking rights on their importance; and proportionality.
I propose another fundamental rule regarding crime: the criminal, or invader, loses his own right to the extent that he has deprived another man of his. If a man deprives another man of some of his self-ownership or its extension in physical property, to that extent does he lose his own rights.5 From this principle immediately derives the proportionality theory of punishment — best summed up in the old adage: "let the punishment fit the crime"
In general, Rothbard's views of speech are pretty nuanced - for example, he makes a clear distinction between agitator who incites a riot (protected speech) vs. conspirator who plans a riot (crime).
Negative rights are rights which the government can't negate. For example, by passing a law against expressing a particular opinion. So a negative right to free speech is one that the government can't take away. But if I go to a party at your house and say something offensive, you can tell me to leave. You have a positive right to solitary enjoyment of your property (contested--some branches of libertarianism allow for positive enforcement of laws like this and some don't), so I have to leave when asked. If I don't, you may take criminal or civil actions against me (which may depend on the exact branch of libertarianism under which the law is written).
If you come to a party at my house and I say something offensive, then the responsibility would then be on you to leave. You couldn't make me leave, as I have a negative right not to be removed from my property. You don't have an equivalent right not to be offended on my property.
There can of course be exceptions. For example, if you rent my property from me, then you may be able (check your rental contract) to eject me from my property. This is because the rental contract temporarily transfers some control from me to you.
I have trouble with the formulation "negative right to good health". You have a negative right to not have your health negatively impacted by me. But in general, you don't have a negative right to good health; you have a negative right against bad impacts on health. This is because in general, I can't give you good health and your health isn't guaranteed to be good absent interaction with me.
It's also worth noting that I don't have an absolute right to free speech. I can't cry fire in a crowded theater in current law. Many libertarians are happy with that, although others would argue that the listener should know enough to look for smoke before panicking. If utterances of mine were actually physically harmful to you, then the obvious answer would be for us not to talk.
Another analogy: I have the right to use a knife to cut meat. But if I use the same knife to cut your living tissue, then your right not to be cut trumps my right to use the knife (ignoring self defense and related exceptions). Circumstances do matter.
There may be some branches of libertarianism that view the right to free speech as more absolute. Part of that though may be the essentially theoretical nature of this question. The general belief is that utterances by me cannot hurt you in and of themselves. They may lead to impacts that cause harm (e.g. incitement to violence or false statements that lead you into some form of harm), but they do not cause direct harm by the simple act of saying them.
Anyway, a number of libertarians might be very skeptical of such a claim of physical harm as a result of free speech.