In ancient times, there had been animal sacrifices at various Yagyas and rituals were performed by Brahmins for kings, while on the other hand they also used to advocate non-violence and preferred a vegetarian diet. How did these contradicting things coexist?
Animal sacrifice, when performed properly according to Vedas, is an exception to the general rule about not harming living beings. Here is what Adi Shankaracharya says in his commentary on the Brahma Sutras:
We proceed to refute the remark made by the pûrvapakshin that sacrificial works are unholy because involving harm done to animals ... Now from scripture we derive the certain knowledge that the gyotishtoma-sacrifice, which involves harm done to animals (i.e. the animal sacrifice), &c., is an act of duty; how then can it be called unholy?--But does not the scriptural precept, 'Do not harm any creature,' intimate that to do harm to any being is an act contrary to duty?--True, but that is a general rule, while the precept, 'Let him offer an animal to Agnîshomau,' embodies an exception; and general rule and exception have different spheres of application.
Ramanujacharya, in his commentary on the Brahma Sutras here, goes further and argues that animal sacrifice is not even contrary to the principle of Ahimsa, because the animal experiences rewards in the afterlife which far outweigh the momentary suffering it experiences:
For Scripture declares that the killing of sacrificial animals makes them to go up to the heavenly world, and therefore is not of the nature of harm. This is declared in the text, 'The animal killed at the sacrifice having assumed a divine body goes to the heavenly world'; 'with a golden body it ascends to the heavenly world.' An action which is the means of supreme exaltation is not of the nature of harm, even if it involves some little pain; it rather is of beneficial nature.--With this the mantra also agrees: 'Thou dost not die, thou goest to the gods on easy paths; where virtuous men go, not evil-doers, there the divine Savitri may lead thee.' An act which has a healing tendency, although it may cause a transitory pain, men of insight declare to be preservative and beneficial.
So it would be like taking your kid to the dentist; they may temporarily suffer some pain, but in the long-run it's beneficial.
As I discuss in this question, Madhvacharya and Baladeva Vidyubhushana, the Dvaita and Gaudiya Vaishnava commentators on the Brahma Sutras, say much the same thing. In any case, this is largely a moot point, because almost no one performs the animal sacrifices described in the Vedas anymore. (This is due to a variety of factors like the rise of Buddhism and Jainism and the substitution of corn-flour animals by Madhvacharya.) Pretty much the only animal sacrifices performed in India nowadays are to goddesses like Kali, but I don't know of any statements in the Vedas that grant a similar exception to the principle of Ahimsa in that case.
Let me add the quote from the Vachanamrut (lessons given by Bhagavan Swaminarayan)
A similar type of question has been asked to Bhagavan Swaminarayan by the Saints and Munis, while Maharaj (Bhagavan Swaminarayan) was answering question about the Dharma and then the discussion goes on and after that Saints have asked this question:
“Mahãrãj, we would like to put the same question to you. Violence (hinsã) performed on animals, as part of a sacrifice or some other ritual, is considered to be dharma. But, non-violence (ahinsã) is also considered to be dharma. Please clarify this.”
Then Bhagavan Swaminarayan answered:
Shreeji Mahãrãj then explained, “Dharma involving violence is for the attainment of dharma, arth, and kãm. Moreover, the dharma which permits violence is for the purpose of limiting violence.
Non- violence, on the other hand, is for the attainment of Moxa...
Dharma involving violence is for only fulfilling worldly desires, but it is not for the attainment of kalyãn(Moxa), whereas non-violence is solely for the purpose of attaining kalyãn(Moxa).
To conclude he told:
Therefore, for both grahasthas and tyãgis only Dharma with non-violence has been cited for the attainment of kalyãn. For example, Uparichar-Vasu Rãjã ruled over a kingdom and still followed a non-violent lifestyle....
Talk goes on.
Everything I have mentioned here is quoted from Vachanamrut (Gadhada Pratham - 69)
Vedas nowhere prescribe the animal sacrifice. It is prohibited in Vedas as well as Vedangas.
Atharvaved 10:1:29. The slaughter of an innocent, O Krityā, is an awful deed. Slay not cow, horse, or man of ours. In whatsoever place thou art concealed we rouse thee up there- from: become thou lighter than a leaf.
Rigveda 10:87:16.The fiend who smears himself with flesh of animlas, with flesh of horses and of human bodies, Who steals the milch-cow's milk away, O Agni,-tear off the heads of such with fiery fury.
Atharvaved 7:5:5.If imprudent yajaman do the yajna by the organs of animals or cows, then this action is foolish and condemnable. Those who know the great process of Yajna through the mind, only the great sage who knows such self-sacrifice, should tell the nature of God.
No, vedas do not mention killing of animals during sacrifice.
Brahmana texts & shrauta sutra texts on Ashwamedha Yagya only mention presence of knife during ritual, nowhere do they mention usage of knife for killing the animal.
Killing of animal is only symbolic as described by satapatha brahmana 188.8.131.52:
atha punaretyāhavanīyamabhyāvṛtyāsate | nedasya saṃjñapyamānasyādhyakṣā asāmeti tasya na kūṭena praghnanti mānuṣaṃ hi tanno eva paścātkarṇam pitṛdevatyaṃ hi tadapigṛhya vaiva mukhaṃ tamayanti veṣkaṃ vā kurvanti tannāha jahi mārayeti mānuṣaṃ hi tatsaṃjñapayānvaganniti taddhi devatrā sa yadāhānvagannityetarhi hyeṣa devānanugacati tasmādāhānvaganniti
15. They then step back (to the altar) and sit down turning towards the Ahavaniya, “lest they should be eye-witnesses to its being quieted (strangled).” They do not slay it on the frontal bone, for that is human manner; nor behind the ear, for that is after the manner of the Fathers. They either choke it by merely keeping its mouth closed, or they make a noose. Therefore he says not, “Slay! kill!” for that is human manner, but, “Quiet it! It has passed away!” for that is after the manner of the gods. For when he says, “It has passed away,” then this one (the Sacrificer) passes away to the gods: therefore he says, “It has passed away.”
From above verses it can be seen that it is the mouth (mukham) of the animal that is covered with a cloth or noose. Now an animal dies of suffocation only when its nose is closed. Closing the mouth of the animal will not suffocate animal, it only chokes the voice of animal resulting in little or no sound leading to quieting of animal. This is what is referred in above verses as symbolic killing.
So wherever vedas say kill the animals it means quieting the animal.
mahAbhArata ashwamedha parva XCI condemns killing of animals during animal sacrifice rituals i.e. literal interpretation of killing in vedic texts :
Formerly, on one occasion Sakra performed a particular sacrifice. While the limbs of the sacrifice were spread out, the Ritwijas became busy in accomplishing the diverse rites ordained in the scriptures. The pourer of libations, possessed of every qualification, became engaged in pouring libations of clarified butter. The great Rishis were seated around. The deities were summoned one by one by contented Brahmanas of great learning uttering scriptural Mantras in sweet voices. Those foremost of Adhwaryyus, not fatigued with what they did, recited the Mantras of the Yajurveda in soft accents. The time came for slaughtering the animals. When the animals selected for sacrifice were seized, the great Rishis, O king, felt compassion for them. Beholding that the animals had all become cheerless, those Rishis, endued with wealth of penances, approached Sakra and said unto him, 'This method of sacrifice is not auspicious. Desirous of acquiring great merit as thou art, this is verily an indication of thy unacquaintance with sacrifice. O Purandara, animals have not been ordained to be slaughtered in sacrifices. O puissant one, these preparations of thine are destructive of merit. This sacrifice is not consistent with righteousness. The destruction of creatures can never be said to be an act of righteousness.
mahAbhArata shAntI parva CCCXXXVII gives an example of ashwamedha where animals were not slain:
King Uparichara, otherwise called Vasu, became a disciple of Vrihaspati and soon became the foremost of his disciples. Admitted as such, he began to study at the feet of his preceptor that science which was composed by the seven Rishis who were (otherwise) known by the name of Chitrasikhandins. With soul cleansed from all sorts of evil by sacrifices and other religious rites, he ruled the Earth like Indra ruling the Heaven. The illustrious king performed a great Horse-sacrifice in which his preceptor Vrihaspati became the Hota. The sons of Prajapati (Brahman) themselves, viz., Ekata, Dwita, and Trita, became the Sadasyas in that sacrifice. 2 There were others also who became Sadasyas in that sacrifice, viz., Dhanusha, Raivya, Arvavasu, Parvavasu, the Rishi Medhatithi, the great Rishi Tandya, the blessed Rishi Santi, otherwise called Vedasiras, the foremost of Rishis, viz., Kapila, who was the father of Salihotra, the first Kalpa, Tittiri the elder brother of Vaisampayana, Kanwa, and Devahotra, in all forming sixteen. In that great sacrifice, O monarch, all the requisite articles were collected. No animals were slain in it. The king had ordained it so. He was full of compassion. Of pure and liberal mind, he had cast off all desires, and was well-conversant with all rites.
As per shanti parva CCLXIII, violent method of performing animal sacrifice is not prohibited but it is only for materialistic results. Only non-violent animal sacrifice leads to moksha :
Of one class of Sacrificers there is return. Of those, however, that are truly wise, there is no return. Although both classes of sacrificers, O Jajali, proceed along the path trodden by the deities (in consequence of the sacrifices they perform), yet such is the difference between their ultimate ends.