We currently live in the Kali Yuga, at least according to the Hindu conception of time. At the end of it, Kalki is supposed to descend, destroy evil, and bring an end to this mahayuga.
But there are many Kali Yugas - one for each mahayuga. Does Kalki appear at the end of each one, or does he only appear at the end of this one?
No, Kalki only comes in this Kali Yuga, not every Kali Yuga. Let me first explain a bit about Hindu timescales. The four Yugas known as Satya, Treta, Dwapara, and Kali together make up one Mahayuga, and a thousand Mahayugas make up one Kalpa or day of Brahma. But in addition to being divided into 1000 Mahayugas, a Kalpa is also divided into fourteen Manvantaras, each of which is made up of about 71 Mahayugas. We're currently living in the seventh Manvantara of the present Kalpa, known as the Vaivasvata Manavantara, and we're living in the 28th Kali Yuga of the Vaivasvata Manvantara.
Now that we have some background, in this chapter of the Matsya Purana (an important Hindu scripture), various incarnations of Vishnu in the present Vaivasvata Manvantara are described. But Kalki is only mentioned once, and that is in the current Kali Yuga. This excerpt from the Skanda Purana says the same thing.
And we can find explicit references to how Kali Yugas have ended in the past. In particular, this chapter of the famous Hindu epic the Mahabharata describes how Vishnu's incarnation Parashurama brought about the end of the 19th Kali Yuga of the Vaivasvata Manvantara by killing the kings of the world:
Even the great ascetic Rama, the hero worshipped by all heroes, that son of Jamadagni, of great fame, will die, without being contented (with the period of his life). Rooting out all evils from the earth, he caused the primeval Yuga to set in. Having obtained unrivalled prosperity, no fault could be seen in him. His father having been slain and his calf having been stolen by the Kshatriyas, he without any boast, slew Kartavirya who had never been vanquished before by foes. With his bow he slew four and sixty times ten thousand Kshatriyas already within the jaws of death. In that slaughter were included fourteen thousand Brahmana-hating Kshatriyas of the Dantakura country, all of whom he slew. Of the Haihayas, he slew a thousand with his short club, a thousand with his sword, and a thousand by hanging. Heroic warriors, with their cars, steeds, and elephants, lay dead on the field, slain by the wise son of Jamadagni, enraged at the slaughter of his father. And Rama, on that occasion, slew ten thousand Kshatriyas with his axe.
In fact, as far as I know there was only one other occasion where Vishnu took a Kalki incarnation. The Kalki incarnation was named Pramati, and he seems to have lived in the Swayambhuva Manvantara, the first Manvantara of the present Kalpa. (The Kalki incarnation who is going to come in present Kali Yuga will be named Vishnuyasha.)
By the way, if you're interested in those lists of Vaivasvata Manvantara incarnations found in the Matsya and Skanda Puranas, I've posted a few questions about them on Hinduism.SE, here, here, and here.
