English-speaking peoples, to use Winston Churchill's phrase, have been dealing with this problem off and on for 300 years. In the late 17th century, most of continental Europe had established state churches and prohibited or disfavored other worship. England had an established church but also tolerated other forms of worship, including by Jews who were invited back into the country by Oliver Cromwell.
But the English people regarded the Catholic Church as a threat to their liberty. The English saw the great hegemon of the age, Louis XIV, as expanding the zone of intolerance through foreign invasion and the withdrawal in 1685 of tolerance of the Protestant Huguenots. An earlier pope had called for the murder of Queen Elizabeth I, and a perennial English bestseller was "Foxe's Book of Martyrs," recounting the persecution of Protestants under her Catholic predecessor Mary I. So after the Catholic King James II was ousted in the Glorious Revolution of 1688-89, Parliament passed a Toleration Act that explicitly refused Catholics the right to hold public office or serve as military officers. There was a widespread belief that a Jesuit doctrine entitled Catholics to falsely swear oaths of loyalty if they had a "mental reservation." Catholics, in this view, were intolerant and could not be trusted even if they swore they were not.
America's Founding Fathers took a different view. Their Constitution said there could be no "religious test for office," as there was in Britain. But the oath of the vice president, written by the First Congress, requires him to swear that he has "no mental reservation." It's unrecorded whether the Catholic Joe Biden understood the origin of this phrase when he took the oath in 2009 and 2013.
In the 20th century, the problem of how far to tolerate intolerance flared with the growth of a significant Communist movement subordinate to the totalitarian Soviet Union. Some Communists proclaimed themselves as such openly. But others denied their beliefs, particularly when, as in much of the 1930s and even more so after World War II, the Soviet Union emerged as an adversary of the United States.
Congress responded in 1940 by making it a crime to advocate the violent overthrow of the United States. Free speech advocates argued this went too far; violent revolutionary actions might be proscribed, but people should not be punished for uttering words. I tend to take this view, but there are obviously serious arguments on both sides.
The anti-Communist movement has been discredited by some mistakes made by Sen. Joseph McCarthy. McCarthy was correct in saying that secret Communists had held high positions in the Roosevelt administration. But most Communists had been ousted from government, the Democratic Party and major labor unions by the Truman administration and anti-Communist liberals such as Eleanor Roosevelt, Walter Reuther, Hubert Humphrey and Ronald Reagan in the late 1940s. Humphrey even sponsored a bill to explicitly outlaw the Communist Party.
The lesson is that tolerant societies sometimes feel the need to take extraordinary and otherwise repellent measures, to combat secretive, conspiratorial forces that seek to impose systematic intolerance -- totalitarian Communism or jihadist sharia.
After the Charlie Hebdo murders, France and other European countries -- and the United States as well -- seem likely to step up surveillance, prosecution and expulsion of jihadists in their midst. This will be questioned by some as prompted by racism (though jihadist Muslims are not a race) or Islamophobia. Some, perhaps including Barack Obama, continue to see the threat of a so far nonexistent backlash against all Muslims as greater than the threat of further jihadist attacks.
European nations seem likely to recoil from a vaguely defined multiculturalism that endorses the isolation of Muslim communities and toward the sense, long stronger in America, that potentially intolerant immigrants should assimilate toward national norms of toleration.
Those actively protecting a tolerant society from the intolerant will sometimes make mistakes or go too far. It's impossible to prevent that from happening; it's important to try to prevent it from happening very often. That's the tragic challenge that tolerant societies under attack from the intolerant have faced in the past and face again today.