I am cheating a little to give this answer, because I am fairly sure that it is part of Gil's motivation in asking the question.  The most natural generalization of the Birkhoff hypothesis to quantum probability is only true for qubits.  (It might also be true for a qubit tensor a classical system; I did not check that case.)

A quantum measurable space is a von Neumann algebra.  We are most interested in the finite-dimensional case, where classically "measurable space" is just a fancy name for the random variables on a finite set.  A finite-dimensional von Neumann algebra is a direct sum of matrix algebras.  In particular, $M_2$ is called a qubit and $M_d$ is called a qudit.

To make a long story short, the Birkhoff hypothesis can be stated for a direct sum of $a$ copies of $M_b$, or $aM_b$.  In this setting, a doubly stochastic map $E$ is a linear map from $aM_b$ to itself that preserves trace, that preserves the identity element, and that is completely positive.  In this setting, $E$ is completely positive if it takes positive semidefinite elements of $aM_b$ to positive semidefinite elements, and if $E \otimes I$ also has that property on the algebra $aM_b \otimes N$ for another von Neumann or $C^*$-algebra $N$.  The natural analogue of permutation matrices are the *-algebra automorphisms of $aM_b$.  These are permutations of the matrix blocks, composed with maps of the form $E(x) = uxu^*$, where $u$ is a unitary element of $aM_b$.  The question as before is whether the doubly stochastic maps are the convex hull of the automorphisms.

This Birkhoff hypothesis is true for $M_2$, false for $M_d$ for $d \ge 3$, and I should check it for $nM_2$.  It is true for $aM_1 = a\mathbb{C}$, because then it is the usual Birkhoff-von Neumann theorem.

I am left wondering about two infinite classical versions of Birkhoff's theorem, for the algebras $\ell^\infty(\mathbb{N})$ and $L^\infty([0,1])$.  In the former case, one would ask whether any stochastic map that preserves counting measure (even though counting measure is not normalized) is an infinite convex sum of permutations of $\mathbb{N}$.  In the latter case, whether any stochastic map that preserve Lebesgue measure is a convex integral of measure-preserving permutations of $[0,1]$.

----------

Since Gil asks for a reference, a recent one is [Unital Quantum Channels - Convex Structure and Revivals of Birkhoff's Theorem][1], by Mendl and Wolf.

  [1]: http://arxiv.org/abs/0806.2820