Since you don't want partial translucency: just discard pixels with an alpha of less than 0.5. As a bonus you won't even need to sort quads since there isn't any blending involved, the depth buffer by itself is enough.
EDIT: oh, I see what you mean. But the method still works for linear filtered textures (for example, look at the trees in Super Mario 64 - yes, it's the same method). If you want partial translucency then you have no option but to do proper blending.