Concise proof that every common divisor divides GCD without Bezout's identity?

One easy and insightful way is to use the proof below. It essentially constructs $\rm\:gcd\:$ from $\rm\:lcm\:$ by employing duality between minimal and maximal elements - see the Remark below. This is essentially how the linked Wikipedia proof works, but there the innate duality is obfuscated by the presentation. Below is a proof structured so that this fundamental duality is brought to the fore.

$\rm{\bf Theorem}\quad c\mid a,b\iff c\mid d,\ \ $ for $\rm\ \ d = ab/lcm(a,b).\ $ $\rm\color{#0a0}{Hence}$ $\rm\ d = gcd(a,b)$

$\rm{\bf Proof}\qquad\ \ \, c\mid a,b \iff a,b\mid ab/c \iff lcm(a,b)\mid ab/c \iff c\mid ab/lcm(a,b)$

$\rm\color{#0a0}{Generally}\,$ if $\rm\, c\mid a,b\iff c\mid d\ $ then $\rm\ d = \gcd(a,b)\ $ up to unit factors, i.e. they're associate.

Indeed setting $\rm\:c = d\:$ in direction $(\Leftarrow)$ shows that $\rm\:d\mid a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b.\:$ Conversely, by direction $(\Rightarrow)$ we deduce that $\rm\:d\:$ is divisible by every common divisor $\rm\:c\:$ of $\rm\:a,b,\:$ thus $\rm\:c\mid d\:\Rightarrow\: c\le d,\:$ so $\rm\:d\:$ is a greatest common divisor (both divisibility and magnitude-wise).

Remark $\ $ The proof shows that, in any domain, if $\rm\:lcm(a,b)\:$ exists then $\rm\:gcd(a,b)\:$ exists and $\rm\ gcd(a,b)\,lcm(a,b) = ab\ $ up to unit factors, i.e. they are associate. The innate duality in the proof is clarified by employing the involution $\rm\ x'\! = ab/x\ $ on the divisors of $\rm\:ab.\:$ Let's rewrite the proof using this involution (reflection).

Notice that $\rm\ x\,\mid\, y\:\color{#c00}\iff\: y'\mid x'\,\ $ by $\smash[t]{\,\ \rm\dfrac{y}x = \dfrac{x'}{y'} \ }$ by $\rm\, \ yy' = ab = xx',\ $ so rewriting using this

$\begin{eqnarray}\rm the\ proof\ \ \ c\mid a,b &\iff&\rm b,\,a\mid ab/c &\iff&\rm lcm(b,\,a)\mid ab/c &\iff&\rm c\mid ab/lcm(b,a)\\[.5em] \rm becomes\ \ \ \ c\mid a,b &\color{#c00}\iff&\rm a',b'\mid c' &\iff&\rm lcm(a',b')\mid c' &\color{#c00}\iff&\rm c\mid lcm(a',b')'\end{eqnarray}$

Now the innate duality is clear: $\rm\ gcd(a,b)\,=\,lcm(a',b')'\ $ by the $\rm\color{#0a0}{above}$ gcd characterization.

We can gain some insight by seeing what happens for other rings. A GCD domain is an integral domain $D$ such that $\gcd$s exist in the sense that for any $a, b \in D$ there exists an element $\gcd(a, b) \in D$ such that $e | a, e | b \Rightarrow e | \gcd(a, b)$. A Bézout domain is an integral domain satisfying Bézout's identity.

Unsurprisingly, Bézout domains are GCD domains, and the proof is the one you already know. It turns out that the converse is false, so there exist GCD domains which are not Bézout domains; Wikipedia gives a construction.

(But if you're allowing yourself the division algorithm, why the fuss? The path from the division algorithm to Bézout's identity is straightforward. In all of these proofs for $\mathbb{Z}$ the division algorithm is doing most of the work.)

Proof using linear diophantine equations; Note: if d=gcd(a,b), then there exist integers x and y such that d=ax+by.

Suppose c|a and c|b and d=gcd(a,b). Then, by definition of divisibility, a=cl & b=ck, for some integers l & k. By definition of gcd, d=ax+by for some integers x & y. By subsitution, d=(cl)x + (ck)y =clx + cky =c(lx+ky) =cm by closure, with m=lx+ky. Therefore d=cm But by definition of divisibity, this implies c|d and m|d Therefore c|d QED :)