Local Fermionic Symmetry That is perhaps a bit of an advertisement, but a couple of collaborators and myself just sent out a paper, and one of the results there is a little bit surprising. We found (in section 6E) a fermionic local symmetry which closes to a tensor gauge symmetry and therefore does not imply (contrary to common lore) the presence of gravity. The construction is in the context of the six dimensional (2,0) theory, and uses in an essential way properties of chiral fermions in six dimensions, but one has to wonder if this is more general. 
So my question is simple - does this ring a bell? are there any other known examples?
 A: Congratulations to your cute and solid paper and your new loophole that is morally on par with a loophole circumventing the Coleman-Mandula theorem itself – almost. ;-) 
I am confident you did the algebra correctly so let me offer you the form of the lore that I usually present and the way how you circumvented it.
The lore says that the local fermionic transformations are generated by the density of a locally conserved quantity – the supercharge: and you may call it this way in your case, too. The anticommutator of such supercharges must be a "spacetime vector" of a sort and this statement must hold at the level of the densities, too.
However, one must be careful what is the "spacetime vector" and how many components of it are participating in the algebra. Normally, the lore assumes that the "real large spacetime dimensions" i.e. the momenta and energies must be included on the right-hand side of the fermionic anticommutator algebra. When localized, this would inevitably lead to a gravitating theory.
Nevertheless, it's not strictly necessary that all components of a spacetime vector are included on the right hand side in this way and it's not true that the energy-momentum is the only conserved quantity that transforms as a vector. As your example shows, one may split the 11 dimensions of M-theory and the "necessary appearance of a vector-like generator" on the right hand side doesn't have to include the regular momentum along the M5-brane directions at all.
Instead, your example has different things that transform as a vector, but they're not the energy-momentum. Instead, they're the "winding charge of the boundary of an M2-brane" or the density of the "self-dual strings" dissolved within your M5-brane. This "winding charge" is a heuristic way how to describe the generator of the 
$$\delta B_{\mu\nu} (x) = \partial_\mu \lambda_\nu (x) - \partial_\nu \lambda_\mu (x)$$
local gauge transformation for the two-form potential. Much like the regular electromagnetic gauge transformations are generated by a density of the electric charge, these extended $p$-form transformations are generated by densities of various strings and branes' winding and wrapping numbers.
So the algebraic requirement of having the density of a vector on the right hand side is protected and this part of the lore is preserved; however, you debunk the assumption of the lore that the conserved vector has to be energy-momentum. Instead, your conserved vector is a sort of the winding number of the self-dual string and its density enters the right hand side.
Let me note that having at least 2 of the minimal spinors of supercharges is a necessary condition for you to be able to avoid the energy-momentum: with extended (chiral) supersymmetry like the (2,0) supersymmetry, you may get purely "central charges" on the right hand side and send the coefficient of the normal energy-momentum to zero. The minimal ${\mathcal N} = 1$ supersymmetry doesn't have any central charges so the energy-momentum (and therefore gravity, in the local case) has to appear on the right hand side. The lore has therefore incorrectly generalized the experience from the minimal supersymmetry, not acknowledging that the energy-momentum and central-charge terms in supersymmetry algebras may "decouple" and beat each other in different ways.
