Can mortise and tenon joints be strong without glue?
You could use one of the many variations of the mortise and tenon joint, depending on the look you're going for. Though I agree with HerrBag, that the strength of a mortise and tenon joint should not rely on glue.
Tusk Tenon
This is a through tenon variation, where a wedge is used to lock the joint together.


Fox tail (Wedged) Tenon
This is another through variation, though the tenon ends up flush on the outside of the joint.  In this joint slots are cut into the tenon. and wedges are driven into the slots after assembly. This causes the tenon to expand, and tighten in the mortise.  Usually the mortise will be slightly tapered, to allow additional expansion and to create a stronger joint.