Only more public awareness of concordats will make it politically possible to get rid of them. Until then, most politicans will remain more afraid of displeasing the Vatican than of protecting the rights of their own electorate. Yet in 2016, about 400 people demonstrated against their country's concordats in the very Catholic Croatia.
Kings cancel concordats
Kings of the past sometimes found it easier to resist Vatican pressure than modern politicians do, especially when they weren't Catholic.
It was the Reformation which cleared concordats from Northern Europe. The Concordat of Vienna made in 1448 with the Holy Roman Empire of the German Nation had ensured a flow of gold from Germany to Rome. These were the annates, or first-fruits of a benefice. Martin Luther denounced this as "Roman avarice", Ulrich von Hutten called it "a good fat robbery" and the desperately poor German peasants rebelled in the name of freedom. In the end the peasants were betrayed: it was only the princes who won religious freedom. After 1555 each prince in the Holy Roman Empire got to determine the faith of his subjects, and according to the fortunes of war, people were forced to switch back and forth from one religion to another. Like the rest of Europe, each of the several hundred principalities in Germany had its own "state church".
However, in the long run the Reformation did more than change the state religion in Northern Europe from Catholic to Protestant, for wider forces were at work. Printed books were now available, including Bibles translated by the reformers into the languages of the people, and more people were able read them.
This gave them access to two, often seemingly contradictory, sources of religious authority: the Bible and the Church. The religiousm Reformers' verdict on these sources is depicted in a 17th-century English woodcut, "The Bible weighs more". 
The Reformers objected to all papal "decrees and decretals" which are pictured on the right-hand scale pan, surrounded by other tokens of what Luther called "papal paganism".  Together they are weighed against the Bible in the left-hand scale pan. (This alludes to the common mediaeval image of St. Michael weighing souls, to assess their conduct in life, in order to assign them to heaven or hell.) Since concordats were not to be found in the Bible, to the Reformers they were merely part of the Church tradition on the right-hand scale pan which was to be swept away.
Luther's influence soon spread beyong the princes of Germany. Christian III, King of Denmark and Norway, had watched Martin Luther defend his beliefs before Church authorities and seen him outlawed as a result. However, when Christian carried out the Protestant Reformation in Denmark and Norway, the pope could do nothig to stop him. As a result, in 1534 the Norwegian concordat became a dead letter.
The next year King Henry VIII of England proclaimed the Protestant Reformation in his kingdom, too. This nullified the Concordat of London. Pope Sixtus V treated the Spanish attempt to conquer Engliand as a holy crusade. However, the loss of the Spanish fleet kept Catholicism from being reinstated as the state religion there.
The rift between the pope and the tsar began in 1863 when his Polish Catholic subjects rebelled. Alexander removed their clergy whom he believed were stirring up the unrest. Pius IX then issued a formal condemnation of the tsar. 
The next year the pope made things worse. In 1864 Pius issued an encyclical, Condemning current errors denouncing (among other things) the "impudence" of those unwilling to subordinate the state to the "supreme authority of the Church … given to her by Christ Himself". 
The tsar was not impressed by the idea that any refusal on his part to recognise the Pope as the head of his state was "impudence". For one thing, he was Russian Orthodox and didn't recognise the spiritual authority of the Pope. For another, he outclassed the Pontiff in the temporal realm. True, at this time Pius still reigned over the remaining Papal States which surrounded Rome (and was apparently even hoping to become the head of a united Italy ). However, the Russian Empire was considerably larger than the increasingly threatened Papal States. And, of course, the tsar even had far more titles than the pope. He was "Emperor and Autocrat of All the Russias", Grand Duke of Finland, King of Poland and had some 60 additional honourifics.
Not surprisingly then, in 1867 Russia abrogated the concordat which it had concluded twenty years earlier with the same pope.
However, Pius IX remained undaunted and proceeded to scuttle another concordat. In 1870 he had himself proclaimed infallible. He bullied the only cardinal who dared to disagree with him in public and placed the works of doubters on the Index of Forbidden Books.  He also empowered Catholic bishops worldwide to punish those who refused to accept this.
The rights of citizens under the constitution were not compatible with the clause of the Concordat which insisted that all teachers in schools were to be Catholics. A new law left the authorities of a denomination the right to ensure that the teachers of religion in a school were of their own denomination. In 1868 the State introduced civil marriage (by a law which the Pope denounced as 'abominabilis'), not as compulsory, but available to citizens who did not want a Church wedding. An apostate from Christian faith was no longer excluded from the law of inheritance. If someone taught what was against the Christian religion it was no longer an offence punishable by the State. 
Franz Joseph I had concluded the concordat with Pius IX in 1855 when the Pontiff's pretensions appeared (somewhat) more modest. But after Pius broadcast his new claim the Austrian government decided that if one of the parties to an agreement became infallible, this amounted to a "fundamental change of circumstances" which undermined the validity of any treaty. On 19 July 1870, therefore, Austria declared the Concordat to have been abrogated by the pope himself. Two years later, Switzerland, having no concordat to cancel, reacted to Pius's new infallibility by breaking off its diplomatic relations with the Vatican altogether. 
Seldom does the Vicar of Christ shoot himself in the foot with the astonishing regularity of Pius IX. However, even when a much more adroit diplomat occupies the Throne of St. Peter, there are still ways to get rid of concordats.
Communist governments abolish concordats
Communist governments also routinely cancelled concordats without the sky falling in. When Poland came under the Soviet sphere of influence, the Interim Government of National Unity unilaterally terminated the Concordat on 12 September 1945. The 1952 Constitution separated church and state and proclaimed freedom of religion to be a civil right. (At the time it was remarked, “The Constitution is excellent ― a pity it's so rarely applied”.) As in the United States, the legal situation of the Church and its property were provided for in civil laws, rather than through a concordat.
In Asia, the People's Republic of China cancelled diplomatic relations with the Vatican in 1951 and relations with the Socialist Republic of Vietnam have "remained inactive" since 1975.
It is certainly true that in Communist countries and even in post-Communist Georgia there have been legitimate concerns about the lack of religious freedom, but a Vatican concordat is not the way to address these. In fact, in pre-WWII fascist countries concordats often codified a Catholic religious monopoly and these state churches severely limited religious freedom. What is needed is not concordats, but religious freedom for all, in other words the full implementation of Article 18 of the Universal Declaration of Human Rights.
Democratic governments scrap concordatsDemocratic governments have also, on occasion, rejected concordats.
♦ Many Latin American countries scrapped their 19th-century concordats and, as of 2014, some have not replaced them: Costa Rica, Guatemala, Honduras and Nicaragua. Uruguay has never had one.
♦ In 1904 the French National Assembly cancelled the concordat by breaking off diplomatic relations with the Vatican in 1904.
♦ In Georgia it was political pressure by the Orthodox Church that prevented the signing in 2003 of a concordat whose text had been kept secret. At the last moment the President refused to sign the agreement, forcing the Vatican “foreign minister”, Archbishop Tauran, to return home with the document unsigned.
♦ And as recently as 2006 the Slovak foreign minister refused to sign a concordat. Of course, there was a price to pay for defying the Vatican: the Christian Democrats then left the governing coalition, and the Slovak Government fell.
♦ By contrast, the Czech concordat was stalled at the final stage. It had already been signed in 2002 when the following year the Czech Chamber of Deputies legislature rejected it. Now, however, the President who had opposed it is being courted by the Church and the outcome remains uncertain.
♦ Meanwhile in 2010 Venezuela's President Chavez, reacting to the political opposition of the Church, threatened to scuttle the country's 1964 concordat. and he recalled the Venezuelan ambassador to the Vatican. ("Lot of prestige would be lost in the event of breaking with the Holy See", El Universal, 2010-07-19)
♦ In 2005 the Argentine military bishop attacked AIDS prevention by the democratic government, while appearing to make light of the death squads of the former military junta. His remarks made it politically possible for President Nestor Kirchner to threaten to cancel a concordat — the “international treaty” which let the Vatican appoint this military bishop — although it is the taxpayers who provide the bishop’s salary. See Concordat's Military Bishop shocks Argentina, President threatens to end Vatican pact.
♦ And in 2016 a demonstration against concordats was held in Croatia, demanding the government annul “harmful contracts with the Holy See” which cost Croatian citizens more than a billion kuna a year (over 140 million US dollars). They claimed that the country's concordats have turned majority of Croatians into second-class citizens. "We are not all equal before the law because they allow clergy a privileged position at the courts and public institutions, and allow systematic discrimination of groups which Catholic hierarchy also discriminates against – women and LGBT people, and all non-Catholics."
Marijana Bijelić said that Vatican concordats offer no advantages to Croatians, just huge obligations. “We think that the work of the Church in the political field is harmful and represents the abuse of religion to gain political power”, she said. 
Even the Vatican suppressed a concordat (when it realised it could do better)
The Vatican also scrapped a concordat when it realised it could get a better deal by waiting. The Convention between People's Republic of Poland and the Holy See., signed on 4 May 1988 and meant to come into effect just 13 days later was quickly suppressed when the Vatican realised that Communism was collapsing.
In Europe, (Germany in 2007 and Spain in 2009) there have even been the first (so far unsuccessful) attempts to challenge concordats in court. ("Konkordatsklage gescheitert" ["Concordat challenge quashed"], Süddeutsche Zeitung, 2008-12-12; "Un juez cuestiona la legalidad del Concordato ante el TC" ["Judge questions the legality of the Concordat before the Constitutional Court"], El Publico, 2009-05-09.)
However, on those rare occasions where there's the political will to do so, actually getting rid of a concordat seems to pose no problem at all.
1. Woodcut from The Roxburghe Ballads (1676), volume 4, part 1, page 119.
2. Thanks to Berni Lowe for his knowledgeable interpretation of the woodcut:
The rejected items, running clockwise, include a cardinal's hat, a reminder of the "unbiblical" Church hierarchy. Flanking the rosary are a paschal lamb, a crucifix and the statue of a saint. To the Reformers, all of these verged on the golden calf.
The object with the slot on top appears to be a "monstrance", the transparent case of silver or gold in which a "host" or wafer is on permanent display on the Catholic altar. Next comes what looks like an "aspergil", used for sprinkling holy water, and then the bell rung during the mass when the wine and wafer turn into the blood and body of Christ.
After the swords and the papal triple crown comes the pope's insignia, the crossed keys of St. Peter. (The Protestants strongly doubted that these would fit the locks on the gates of heaven.) Then there's one of the tonsured monks whose often riotous lives helped undermine respect for the Church. And finally, the text in the centre may represent the papal "indulgences" which released souls from purgatory — for a fee.
3. Pius IX, Allocution, November 1866. John William Draper, History of the Conflict between Religion and Science, 1875, Chapter 12, p. 334.
4. Pius IX, Condemning current errors, 8 December 1864, §5. http://www.papalencyclicals.net/Pius09/p9quanta.htm
Not to be confused with his handy list of gravely dangerous opinions, A Syllabus of Errors, issued on the same date,"a catalogue of eighty errors of the age, which had been previously pointed out by Pius IX in Consistorial Allocutions, Encyclical and other Apostolic Letters, but are here conveniently brought together". http://www.papalencyclicals.net/Pius09/p9syll.htm
5. §1674: "Edgardo Levi-Mortara's Testimony for Beatification of Pius IX - Rome, Italy", [no date: the author died in 1940], Zenit, 25 September 2000. http://saints.sqpn.com/pope025501.htm
6. For more about this see reviews of August Hasler, How the Pope Became Infallible: Pius IX and the Politics of Persuasion, 1981.
7. "Owen Chadwick, A history of the popes, 1830-1914", 1998. p. 248. Google reprint
8. "Switzerland: Diplomatic relations with the Vatican broken", New York Times, 26 December 1872. http://query.nytimes.com/mem/archive-free/pdf?res=9800E6D9163BEF34BC4051DFB4678389669FDE
9. "Protest against Concordat with the Vatican Held in Zagreb", Total Croatia News, 22 October 2016. https://www.total-croatia-news.com/item/14566-protest-against-concordat-with-the-vatican-held-in-zagreb
This Georgian news story from 2003 recounts the protests over the Vatican concordat which was to be signed after secret negotiations. Orthodox clerics led demonstrations against it and the Vatican's foreign minister, Archbishop Tauran, was obliged to return home with the concordat unsigned.