If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.

You have proved that if $d\mid a$ and $d\mid b$, and $c=ax+by$, then $d\mid c$. That is not at all what we want to show.

The result will be easy once we prove:

Lemma: If $\gcd(a,b)=1$, there exist integers $s$ and $t$ such that $as+bt=1$.

Taking the Lemma for granted temporarily, note that if $as+bt=1$ then $a(cs)+b(ct)=c$, so we can take $x=cs$ and $y=ct$ to prove our result. But the hard part is

Proof of Lemma: We sketch the standard proof. Let $K$ be the set of all positive integers that can be represented in the form $au+bv$, where $u$ and $v$ range over the integers. The set $K$ is non-empty, so has a smallest positive element $k$. So there is a $u_1,v_1$ such that $k=au_1+bv_1$. We show that $k=1$. That will complete the proof.

Suppose to the contrary that $k\gt 1$. The number $k$ cannot divide both of $a$ and $b$, for if it did we would violate $\gcd(a,b)=1$. Without loss of generality we may assume $k$ does not divide $a$. Then $a=qk+r$, for some integers $q$ and $r$ such that $0\lt r\lt k$.

But then $$r=a-qk=a-q(au_1+bv_1)=a(1-qu_1)+b(-qv_1).$$ Since $0\lt r\lt k$, this contradicts the fact that $k$ is the smallest positive integer of the shape $au+bv$.