John Locke's Letter Concerning Toleration is an important early-modern argument for religious toleration, but the principles behind it can be more widely applied (fortunately, for the sake of its relevance to modern society).
Background (Locke's Social Contract theory):
Locke envisaged a pre-political society, known as the "State of Nature", whereby all men are free and in full ownership of their "natural rights" (to life, liberty and property; and the punishment of those who infringe on others' rights). The lack of security and justice within the SoN motivates its inhabitants to join together (by free consent) and form a common community. Each citizen then gives up various rights to the community as a whole (particularly the right of punishment), so that they may all be better protected.
By this conception of the State as arising out of the consent of free men, it is logical to deny the political power any right to interfere in purely private matters.
The inward/outward distinction:
The purpose of civil government is thus clear: to protect and promote our civil interests, i.e. life (health), liberty and property. Government is, according to Locke, concerned only with outward things (but note that this includes both negative and positive rights, such as welfare).
By contrast, the cultivation of the soul, culture, personal identity and other such inward matters (essentially anything which affects our inner life), is considered to be no business of the state.
This seemingly sensible principle has some rather radical implications. It allows the redistribution of income, but disallows the spread or promotion of culture by the state. Public museums, art galleries, liberal (non-technical) education, etc, would all appear to be forbidden.
The arguments for toleration:
Locke had several arguments advocating toleration. One was simply practical - the government cannot change people's inner selves (e.g. convert them to being "true believers"), it is a practical impossibility (so Locke asserts), so there is no use in trying. Salvation can only be obtained through a free choice, so attempts to force people to adopt the "true faith" are vain and even anti-religious. Whilst this is a reasonable argument against religious intolerance, it lacks wider applicability. Persecutors may be more interested in simply repressing the outward expression of that they detest, rather than actually changing the thoughts & beliefs of their target. Such repression is an achievable possibility, so further reasons must be given against it.
The theoretical argument outlined above (regarding the birth of the State and thus the purpose of political power) is now of the utmost importance. It implies that even if backed by majority opinion, a magistrate is not entitled to "correct" the beliefs or identity of a "mistaken" minority group. Civil government has no right to impose knowledge in its citizens. Identity is not the business of the State.
Exceptions - intolerance is sometimes necessary:
Locke expressed the basic principle: "All is tolerated so long as it does not tend to domination over others", which is intuitively pleasing, but on closer examination faces many of the same problems as Mill's "harm principle". The question of what does or does not constitute "domination" is too ambiguous and open to interpretation, for this principle to have any hope of consistent application.
Another general principle Locke expresses is that all (religious) practices should be tolerated unless they present a threat to the proper functioning of the State. On this basis he denounces Catholicism, for a Catholic's duty to the Pope could induce disloyalty to his prince. Locke also refused to tolerate atheism, arguing that without a higher power to hold atheists to their oaths, their promises could not be trusted.
A reviewer from phil-books summarised nicely how we can generalise from Locke's specific concern with religious toleration, to a more general principle of tolerance:
If a state is created for the purposes and by the methods Locke suggests in his Second Treatise, then the men who consent to form such a state retain a significant negative liberty of belief and action. Any of these beliefs or actions must be tolerated by the state unless they fail Locke's criteria for religious toleration, namely, unless they are "prejudicial to other mens rights" or they "break the public peace of societies."