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.