How are the very first telomeres added?
Telomeres are maintained by telomerase (in certain cell types, not all of them) at every replication. So, the answer to your questions "where did that existing telomere come from? And the telomere before that?" is: "because there was already a telomere to extend at the end of this chromosome".

Your questions boil down to "how did telomeres appear in the first place?" (because once telomeres and a maintenance mechanism have been established, they will simply remain unless some major genomic catastrophe happens), and this is a difficult question. As Whitney pointed out in the comments of your question, some hypotheses about the origin of telomeres are discussed in this article.
Interestingly, Drosophila doesn't have telomerase, and maintains telomeres by a transposition mechanism. Somehow this is a clue about how telomeres appeared: Drosophila telomeres could be an intermediate between circular chromosomes and telomerase-based maintenance of linear chromosomes.

This is a complicated topic, but the scientific literature about the appearance of telomeres is fascinating. Some bacteria (Borrelia and Streptomyces taxa) have linear chromosomes, but maintenance mechanisms that have nothing to do with transposition nor telomerase.

Here are some references:


Drosophila: https://doi.org/10.3389/fonc.2013.00112
Borrelia: https://doi.org/10.1146/annurev.micro.112408.134037
Streptomyces: http://link.springer.com/chapter/10.1007/7171_2007_090


If you can read French, you will find more info in the introduction of my PhD thesis.