$\ell_p$-norm preserving Turing machines
This is not a complete answer to the questions, but it is too long to write as a comment.  It expands my previous comment.

The question “What happens to computation if the axioms of quantum mechanics are modified a little?” is addressed in great detail by a fun paper [Aar04] by Scott Aaronson.  I believe that your questions are essentially answered in the first half of Section 2 of [Aar04].

Aaronson shows that if p&gt;0 and p≠2, then a matrix which preserves the p-norm for all vectors is necessarily a generalized permutation matrix (a product of a permutation matrix and a diagonal matrix).  He states that the same holds in the case p=∞.  All these hold for both over ℝ and over ℂ.  Note that this includes the case of p=1: stochastic matrices preserve the 1-norm for nonnegative vectors but not for all vectors in general.

I guess that a probabilistic Turing machine generalized as in [For00] has a generalized permutation matrix as its global transition matrix only if it is a deterministic Turing machine, but I do not have a proof at hand.

Aaronson discusses also several other modifications of the axioms of quantum mechanics in the paper.  For example, if we change the rule of measurement (instead of the set of allowed gates) so that the outcome x occurs with probability |αx|p/∑y|αy|p, where αy is the amplitude of |y⟩, then this “quantum computer” can solve any problems in PP (including NP-complete problems) in polynomial time unless p=2 (Proposition 5).

References

[Aar04] Scott Aaronson.  Is quantum mechanics an island in theoryspace?  In Proceedings of the Växjö Conference “Quantum Theory: Reconsideration of Foundations,” 2004.  arXiv:quant-ph/0401062v2.

[For00] Lance Fortnow.  One complexity theorist’s view of quantum computing.  In Computing: the Australasian Theory Symposium (CATS 2000), pp. 58–72, Jan. 2000.  http://dx.doi.org/10.1016/S1571-0661(05)80330-5