While I'm not sure if this is the first time - so if anyone knows of anything earlier than this, feel free to correct me - but the "Edicts of Ashoka" issued by the Indian Emperor Ashoka sometime during his reign (which lasted from 269 BC to 232 BC) do talk about allowing free discourse between and practice of different religions.

There are multiple translations of the Edicts, so I'll include some of the ones I've found. These particular Edicts are from the "14 Major Rock Edicts," which refers to the fact that they were inscribed onto, well, large rocks.

Note: "King Piyadasi" refers to Emperor Ashoka.

Also note: these Edicts aren't exactly "legislation" in the modern sense of the word. The Maurya Empire really didn't have legislation in the same mold of Peace of Augsburg. We are talking about a very different governing system in a different location during a different time period. These were personal statements of desire issued by a monarch, essentially.

Edict 7:

Translation by Ven. S. Dhammika, a Buddhist monk and lecturer:

Beloved-of-the-Gods, King Piyadasi, desires that all religions should reside everywhere, for all of them desire self-control and purity of heart. But people have various desires and various passions, and they may practice all of what they should or only a part of it. But one who receives great gifts yet is lacking in self-control, purity of heart, gratitude and firm devotion, such a person is mean.

Translation by Horace Hayman Wilson, a 19th century British orientalist:

The beloved of the gods, the Raja Priyadasi, desires that all unbelievers may everywhere dwell (unmolested), as they also wish for moral restraint and purity of disposition. For men are of various purposes and various desires, and they do injury to all or only to a part. Although, however, there should not be moral restraint or purity of disposition in any one, yet wherever there is great liberality (or charity) gratitude will acknowledge merit even in those who were before that reputed vile.

Edict 12:

Dhammika:

Beloved-of-the-Gods, King Piyadasi, honors both ascetics and the householders of all religions, and he honors them with gifts and honors of various kinds. But Beloved-of-the-Gods, King Piyadasi, does not value gifts and honors as much as he values this -- that there should be growth in the essentials of all religions. Growth in essentials can be done in different ways, but all of them have as their root restraint in speech, that is, not praising one's own religion, or condemning the religion of others without good cause. And if there is cause for criticism, it should be done in a mild way. But it is better to honor other religions for this reason. By so doing, one's own religion benefits, and so do other religions, while doing otherwise harms one's own religion and the religions of others. Whoever praises his own religion, due to excessive devotion, and condemns others with the thought "Let me glorify my own religion," only harms his own religion. Therefore contact (between religions) is good. One should listen to and respect the doctrines professed by others. Beloved-of-the-Gods, King Piyadasi, desires that all should be well-learned in the good doctrines of other religions.

Those who are content with their own religion should be told this: Beloved-of-the-Gods, King Piyadasi, does not value gifts and honors as much as he values that there should be growth in the essentials of all religions. And to this end many are working -- Dhamma Mahamatras, Mahamatras in charge of the women's quarters, officers in charge of outlying areas, and other such officers. And the fruit of this is that one's own religion grows and the Dhamma is illuminated also.

Wilson:

The beloved of the gods, king Priyadasi, honors all forms of religious faith, whether professed by ascetics or householders; he honors them with gifts and with manifold kinds of reverence: but the beloved of the gods considers no gifts or honour so much as the increase of the substance (of religion):--his encouragement of the increase of the substance of all religious belief is manifold. But the root of his (encouragement) is this:--reverence for one's own faith, and no reviling nor injury of that of others. Let the reverence be shown in such and such a manner as is suited to the difference of belief; as when it is done in that manner, it augments our own faith, and benefits that of others. Whoever acts otherwise injures his own religion, and wrongs that of others; for he who in some way honors his own religion, and reviles that of others, saying, having extended to all our own belief, let us make it famous;--he who does this throws difficulties in the way of his own religion: this, his conduct, cannot be right. The duty of a person consists in respect and service of others. Such is the wish of the beloved of the gods; for in all forms of religion there may be many scriptures (Sutras), and many holy texts, which are to be thereafter followed through my protection. The beloved of the gods considers no gift or reverence to be equal to the increase of the essence of the religion : and as this is the object of all religions,--with a view to its dissemination, superintendents of moral duty, as well as over women, and officers of compassion, as well as other officers (are appointed); and the fruit of this (regulation) will be the augmentation of our own faith, and the lustre of moral duty.

Sources:

This site has Dhammika's translation of the Edicts.

This document features Wilson's translation, as well as that of James Prinsep, the first person to decipher the Edicts. I left out Prinsep's translation because he is quite verbose, but it is pretty entertaining to read.