A proof of the salamander lemma without Mitchell's embedding theorem? The salamander lemma is a lemma in homological algebra from which a number of theorems quickly drop out, some of the more famous ones include the snake lemma, the five lemma, the sharp 3x3 lemma (generalized nine lemma), etc.  However, the only proof I've ever seen of this lemma is by a diagram chase after reducing to R-mod by using mitchell's embedding theorem.  Is there an elementary proof of this lemma by universal properties in an abelian category (I don't know if we can weaken the requirements past an abelian category)?
If you haven't heard of the salamander lemma, here's the relevant paper: Bergman - Diagram chasing in double complexes.
And here's an article on it by our gracious administrator, Anton Geraschenko: The salamander lemma.
Also, small side question, but does anyone know a good place to find some worked-out diagram-theoretic proofs that don't use Mitchell and prove everything by universal property?  It's not that I have anything against doing it that way (it's certainly much faster), but I'd be interested to see some proofs done without it, just working from the axioms and universal properties.
PLEASE NOTE THE EDIT BELOW
EDIT:  Jonathan Wise posted an edit to his answer where he provided a great proof for the original question (doesn't use any hint of elements!).  I noticed that he's only gotten four votes for the answer, so I figured I'd just bring it to everyone's attention, since I didn't know that he'd even added this answer until yesterday.  The problem is that he put his edit notice in the middle of the text without bolding it, so I missed it entirely (presumably, so did most other people).
 A: $\DeclareMathOperator\Cone{Cone}$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.
A: The first paper on abelian categories is "Exact Categories and Duality" D. A. Buchsbaum. It was published in 1955, two years before Grothendieck's famous Tōhoku paper. You can find it on jstor (DOI). The section 5 is about "fundamental lemmas" such as the Nine Lemma (5.5), the Snake lemma (5.8) and the Five Lemma (5.9). The proofs are direct using the definition of an abelian category (called "exact category" by Buchsbaum, this term was used later by Quillen), in particular they use — of course — no elements. Unfortunately I cannot find the salamander lemma, but lots of basics of homological algebra such as homology, derived functors, satellites. Basically Buchsbaum observed that there is nothing special to module categories treated in Eilenberg–Cartan's landmark book on homological algebra.
A: There's a proof of the snake lemma without elements (a non-elementary proof?) on my (old) website.
Edit: I added a section about the salamander lemma.
Much later edit:  As Charles Rezk points out below (1 2), my proof of the salamander lemma is correct only in a special case.  I will correct the proof when I find the tex file.
What makes working with elements in an abelian category easier than working with objects is that elements of the target of an epimorphism can be lifted to the source.  If your abelian category has enough projectives, then a proof with elements can usually be adapted to one without elements by replacing each element by a surjection from a projective object.  If you don't have enough projectives, you can still get by without elements.  You have to replace the concept of "element" with "epimorphism from something"; then every "element" can still be lifted by passing to a more refined epimorphism.
This is just code for working locally in the topology generated by epimorphisms.  (That it is a topology is implied by AB2.)  Since there are always enough injective sheaves of abelian groups, this gives an exact embedding of any abelian category in an abelian category with enough injectives (or, if we work with "cotopologies", a category with enough projectives).  This permits one to apply the simpler approach outlined above (using projectives) rather than "pro-epimorphisms".
Once one has an embedding in a Grothendieck abelian category (the category of sheaves of abelian groups always is one), it is not much further to a proof of Mitchell's embedding theorem anyway.
A: Perhaps you have already looked in Freyd's 1964 book on Abelian Categories, which is reviewed here?
Although the book is aimed at the proof of Mitchell's embedding theorem, he does go through a number of categorical diagramme chases in chapter 2.
