Q:

What is the current stance of the Catholic Church regarding the legality of non-Catholic religions?

The famous Syllabus of Errors by Bl. Pope Pius IX condemns, among others, that:

In the present day it is no longer expedient that the Catholic religion should be held as the only religion of the State, to the
  exclusion of all other forms of worship.—Allocution "Nemo vestrum,"
  July 26, 1855.
Hence it has been wisely decided by law, in some Catholic countries, that persons coming to reside therein shall enjoy the
  public exercise of their own peculiar worship.—Allocution
  "Acerbissimum," Sept. 27, 1852. - The Syllabus of Pius IX

Therefore, it would seem that Pius IX orders that all religions bar Catholicism are to be declared illegal by the State.
I am confused. While I don’t know about any official modern document of the Church regarding this issue, the Church really, really doesn’t seem to hold such a position nowadays. Instead, St. Pope John Paul II and Pope Francis have both participated in interfaith prayers for peace alongside not only non-Catholic Christians, but also leaders of heathen religions. This seems to me to hardly reconcile with the above condemnations of Pius IX.
My explanation, up to now, was that the Syllabus has never been officially declared infallible and the current activities of modern Popes like the aforementioned prayer for peace and others prove that the Church has shifted its position on this subject and therefore, these points of the Syllabus are no longer in force.
Am I right? At least, they were in force in the beginning of the XX century, because the Catholic Encyclopedia wrote that:

Even should the condemnation of many propositions not possess that
  unchangeableness peculiar to infallible decisions, nevertheless the
  binding force of the condemnation in regard to all the propositions is
  beyond doubt. For the Syllabus, as appears from the official
  communication of Cardinal Antonelli, is a decision given by the pope
  speaking as universal teacher and judge to Catholics the world over.
  All Catholics, therefore, are bound to accept the Syllabus. Exteriorly
  they may neither in word nor in writing oppose its contents; they must
  also assent to it interiorly. - 
  The syllabus of Pius IX

Some questions force themselves into my mind:

Are condemnations 77-78 from the Syllabus of Error still in force, binding all Catholics to adhere to them and agree with them?
Does this mean that the Church wants worship of non-Christian and non-Catholic Christian religions banned by the State?
How to reconcile numerous ecumenical and interfaith activities held by modern popes, like the interfaith prayers for peace with these condemnations?

A:

it would seem that Pius IX orders that all religions bar Catholicism are to be declared illegal by the State.

States are to prevent false religions from publicly spreading their errors, but the false sects can be tolerated. Unlike Islam, Catholicism does not permit States to force-convert its citizens to Catholicism.
In fact, in medieval Christendom when the State recognized the Church as the true religion, Jews were permitted to raise their children in Judaism as long as they did not spread their errors and heresies publicly in society. It is also forbidden to baptize children of unbelievers against their will.
The main point of Pope Pius IX's statements is that States are able to recognize Catholicism as the true religion and are obliged, for the sake of the common good, to suppress false sects and prevent them from spreading their dangerous errors and heresies.
The contradiction you mention between pre- and post-Vatican II teachings on Church-State relations is one reason the Society of St. Pius X (SSPX) and other groups think that Vatican II taught error and was therefore an invalid council. For example, read ch. 11 "Religious Liberty" of the SSPX's founder Abp. Marcel Lefebvre's Open Letter to Confused Catholics.
Compare what I number below in the Vatican II document Dignitatis Humanæ (7 Dec. 1965):

This Vatican Council declares that the human person has a right to religious freedom [1]. This freedom means that all men are to be immune from coercion on the part of individuals or of social groups and of any human power, in such wise that no one is to be forced to act in a manner contrary to his own beliefs, whether privately or publicly [2], whether alone or in association with others, within due limits [3].
  …
  This right of the human person to religious freedom is to be recognized in the constitutional law whereby society is governed and thus it is to become a civil right [2].

to my corresponding numbers in Pope Pius IX's encyclical Quanta Cura:

For you well know, venerable brethren, that at this time men are found not a few who, applying to civil society the impious and absurd principle of "naturalism," as they call it, dare to teach that "the best constitution of public society and (also) civil progress altogether require that human society be conducted and governed without regard being had to religion any more than if it did not exist; or, at least, without any distinction being made between the true religion and false ones." And, against the doctrine of Scripture, of the Church, and of the Holy Fathers, they do not hesitate to assert that "that is the best condition of civil society, in which no duty is recognized, as attached to the civil power, of restraining by enacted penalties, offenders against the Catholic religion, except so far as public peace may require [3]." From which totally false idea of social government they do not fear to foster that erroneous opinion, most fatal in its effects on the Catholic Church and the salvation of souls, called by Our Predecessor, Gregory XVI, an "insanity" [cf. his Mirari Vos],2 viz., that "liberty of conscience and worship is each man's personal right, which ought to be legally proclaimed and asserted in every rightly constituted society [1]; and that a right resides in the citizens to an absolute liberty, which should be restrained by no authority whether ecclesiastical or civil, whereby they may be able openly and publicly [2] to manifest and declare any of their ideas whatever, either by word of mouth, by the press, or in any other way." But, while they rashly affirm this, they do not think and consider that they are preaching "liberty of perdition;"3 and that "if human arguments are always allowed free room for discussion, there will never be wanting men who will dare to resist truth, and to trust in the flowing speech of human wisdom; whereas we know, from the very teaching of our Lord Jesus Christ, how carefully Christian faith and wisdom should avoid this most injurious babbling."4

and to his Syllabus of Errors, which condemned the following:

Every man is free to embrace and profess that religion which, guided by the light of reason, he shall consider true. [1]—Allocution "Maxima quidem," June 9, 1862; Damnatio "Multiplices inter," June 10, 1851.

…
X. ERRORS HAVING REFERENCE TO MODERN LIBERALISM

In the present day it is no longer expedient that the Catholic religion should be held as the only religion of the State, to the exclusion of all other forms of worship.—Allocution "Nemo vestrum," July 26, 1855.
Hence it has been wisely decided by law, in some Catholic countries, that persons coming to reside therein shall enjoy the public exercise [2] of their own peculiar worship.—Allocution "Acerbissimum," Sept. 27, 1852.
Moreover, it is false that the civil liberty [1] of every form of worship, and the full power, given to all, of overtly and publicly manifesting any opinions whatsoever and thoughts, conduce more easily to corrupt the morals and minds of the people, and to propagate the pest of indifferentism.—Allocution "Nunquam fore," Dec. 15, 1856.
The Roman Pontiff can, and ought to, reconcile himself, and come to terms with progress, liberalism and modern civilization.—Allocution "Jamdudum cernimus," March 18, 1861.

(Taken from here, which is nicely color-coded; unfortunately, StackExchange markdown doesn't support colors.)
Despite the SSPX asking for doctrinal clarity, the post-Vatican II magisterium has yet to clarify exactly how Dignitatis Humanæ is in continuity with 19th century popes' magisterial statements. In fact, Cdl. Ratzinger said the Vatican II document Gaudium et Spes is a "counter-Syllabus" of Pius IX's Syllabus of Errors. Since the Church's ordinary and universal magisterium is infallible (i.e., cannot error), it follows that the Vatican II document on this issue is not magisterial.
A dangerous consequence of Dignitatis Humanæ was that States with constitutions that recognized the Catholic Church as the true religion (e.g., Spain) felt compelled to change their constitutions to view all religions equally.
cf. also these encyclicals condemning modern errors

