homological algebra - 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.

And here's an article on it by our gracious administrator, Anton Geraschenko: Click!

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).