A totally non-elementary suggestion which avoids any kind of embedding theorem is to take the derived category of the abelian category, then look at special cases of the octahedral axiom. Let $A, B, C$ be three objects of the derived category, $f: A\rightarrow B, g:B\rightarrow C$ such that $gf=0$. The octahedral axiom says there is a distinguished triangle $Cone(f)\rightarrow C+A[1] \rightarrow Cone(g)\rightarrow Cone(f)[1]$. You should be able to recover the salamander lemma from the long exact sequence of this complex. This should be easiest to see with the reduction in the note Jonathan Wise posted (so $A, B$, and $C$ are 2-term complexes).
Sorry I'm not adding details at the moment -- I haven't checked them, but I'm pretty sure this works. I'll be crushed if it doesn't, since this is what convinced me to embrace the octahedral axiom.
