Perhaps I posted in the wrong forum for this, because I was more wondering whether anyone had done it rather than requesting functions like this be put in Allegro, although it would be handy in the library, and it does involve hacking the Allegro code.
I tried implementing on Thursday without success. I was trying using 16-bit colour where the upper byte is the Z value.
The main thing I thought I would need to do (heavily simplified) was changing the PUT_PIXEL macros which cgfx.c uses from *p = c to if (c > *p) *p = c and change the MASK macros. The other thing you would need would be functions which operate on the upper byte of a sprite, like painting it's z-value. Normally this would be to a constant z, making it a fast operation, although there would also be the possiblilty of some parts being further forward. I was unsuccessful because I was unable to trace into putpixel with a debugger.
Currently my engine runs through each objects draw method, which may add drawing instructions with a z value to a sorted list of such instructions. After going through all the objects (there's a complicated intermediate step, but never mind), it goes though the list (a tree, actually) and executes them all. Because I'm using a variety of sprite and primitive functions, the code for executing these is increased for every drawing function I make available. Of course if my scripting system was working I could just add compiled scripts to do that. A 2D z-buffer would be an easier but slower way to solve the problem.
Using the 3D functions (like quad3d with texture) would be a lot slower than the methods I was attempting, because there are a lot of multiplications, etc which a 1:1 sprite doesn't incur. I'll probably stick with my current method for the moment.