Could we show $1-(x-\frac{x^3}{3!}+\frac{x^5}{5!}-\dots)^2=(1-\frac{x^2}{2!}+\frac{x^4}{4!}- \dots)^2$ if we didn't know about Taylor Expansion?

As Andres says in his comment, you can compare the coefficients of $x^{2k}$ in both quantities.

On the left-hand side, this coefficient is $(-1)^k \sum_{i+j=k-1} \frac 1 {(2i+1)!(2j+1)!}$, while on the right-hand side, it is $(-1)^k \sum_{i+j=k} \frac 1{(2i)!(2j)!}$.

Multiplying both coefficients by $(2k)!$, you are left to prove $\sum \binom {2k}{2i} = \sum \binom {2k}{2j+1}$, i.e. that the number of even subsets of a set of size $2k$ is the number of odd subsets.

This is in fact true for any nonempty set, not only those of even size. To show this combinatorially, pick a distinguished element $x$ of a set $S$ of size $n$. Then given a subset $X \subset S$, map it either to $X \setminus \{ x \}$ or to $X \cup \{x \}$ according to wether $x \in S$ or not. Then you can check that this is a bijection between odd-sized subsets of $S$ and even-sized subsets of $S$.

This boils down to showing $$\tag1\exp(x+y)=\exp(x)\exp(y),$$ where $\exp(x)=\sum_{n=0}^\infty \frac{x^n}{n!}$, which is more or less straightforward: On the left hand side, the coefficient of $x^ny^m$ is ${n+m\choose n}\cdot\frac1{(n+m)!}$ and on the right it is $\frac1{n!}\cdot\frac1{m!}$, and these expressions are equal. Now we find that for real (or in fact arbitrary) $x$ we have $$\tag2\exp(ix)\exp(-ix)=\exp(0)=1.$$ If we denote the expression in parentheses on the left of your equation with $s(x)$ and on the right with $c(x)$, we see that $\exp(\pm ix)=c(x)\pm is(x)$, so that $(2)$ becomes $$c^2(x)+s^2(x)=1.$$