Finding a limit using change of variable- how come it works?
There is a very general result which guarantees such substitutions. Let $\lim\limits_{x \to a}f(x) = L$ exist and let $\lim\limits_{t \to b}g(t) = a$ exist and also assume that $g(t) \neq a$ when $t$ is in a certain neighborhood of $b$ then $\lim_{t \to b}f(g(t)) = L$.
Please understand that the theorem is valid only under the conditions given in the above result and one of the first conditions is that $\lim_{x \to a}f(x)$ exists. If we don't know in advance whether the limit of $f(x)$ exists then how do we make a substitution $x = g(t)$ (in this question we put $x = t + 1$)?
To answer this we need to understand that the substitution $x = g(t)$ ($x = t + 1$) used here is invertible so that we have an inverse substitution $t = h(x)$ ($t = x - 1$) with $x = g(h(x)), t = h(g(t))$ which will allow us to infer the existence of limit $\lim_{x \to a}f(x)$ on the basis of existence of limit $\lim_{t \to b}f(g(t))$ via the theorem given in the beginning of this post.
Another condition which is very very important is to ensure that $g(t) \neq a$ when $t$ is near $b$. Clearly this holds in the substitution used in the current question when $x = t + 1$ and $a = 1, b = 0$.
If we think deeply we will find that if $g(t)$ is invertible in the neighborhood of $t = b$ then it will automatically ensure that $g(t) \neq a$ in a certain neighborhood of $b$. So in practice we use the following :
Theorem: If $x = g(t)$ is an invertible function with inverse $t = h(x)$ in the deleted neighborhood of $t = b$ and $\lim\limits_{t \to b}g(t) = a, \lim\limits_{x \to a}h(x) = b$ then either both the limits $\lim\limits_{x \to a}f(x)$ and $\lim\limits_{t \to b}f(g(t))$ exist and are equal or both of them don't exist.
Note that there is no condition on $f$ for the above theorem.
It works because the equality holds: $$ {x\cos(x-1)-1\over x-1}={(t+1)\cos(t)-1\over t} \quad \text{where }t=x-1.\tag{1} $$ This is no different than rewriting $2+2$ or $3+1$ or $7-3$ whenever you see a $4$. They are just different ways to same the same thing.
Now, since in the original problem, we had $x\to 1$, then in the new variable we have $t=x-1\to 1-1=0$, i.e., $t\to 0$. Hence, $(1)$ becomes $$ \lim_{x\to 1}{x\cos(x-1)-1\over x-1}=\lim_{t\to 0}{(t+1)\cos(t)-1\over t}.\tag{2} $$
You said limits aren't an algebraic equation---that is correct. But they are an "operation" that one can apply to both sides of an existing equation, such as $(1)$ and maintain equality such as in $(2)$.
Edit based on the comments:
Suppose you have the algebraic expression $f(x)$ and make the change of variables $x=g(t)$. Then $$f(x)=f(g(t)).\tag{3}$$ This is a generalized version of the type of statement in $(1)$.
Moreover, if $g$ is a continuous function then $x\to a\implies g(t)\to a$, but then from $(3)$ we see $$ \lim_{x\to a}f(x)=\lim_{g(t)\to a}f(g(t)). $$ which is a generalized version of $(2)$.