Are there constructive examples for doubly stochastic matrices (whose rows and columns all sum up to 1 and contain only nonnegative entries) which are not diagonalizable?

Sure. For example: $$A = \begin{pmatrix} 5/12 & 5/12 & 1/6 \\ 1/4 & 1/4 & 1/2 \\ 1/3 & 1/3 & 1/3 \end{pmatrix}$$ Note that $$A \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1/4 \\ 1/4 \\ 0 \end{pmatrix} \ \mbox{and} \ A^2 \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} = 0.$$ This shows that $A$ is not diagonalizable, as, for diagonalizable matrices, $A$ and $A^2$ have the same kernel. Now, let me explain how to find this. Let $w$ be the all ones vector. The condition that $A$ is doubly stochastic is that $Aw =w$ and $A^T w = w$ (ignoring positivity for now). For any nonzero vector $v \in \mathbb{R}^n$, we have $Av =v$ and $A^T v = v$ if and only if $Av=v$ and $A$ sends $v^{\perp}$ into itself. This equivalence is obvious for $v=e_1$, and the truth of the statement is preserved by orthogonal changes of coordinate, so it is true for any nonzero $v$. So, I wanted $Aw=w$ and $A$ to preserve $w^{\perp}$. So, if $A$ is going to be nondiagonalizable, it has to have a nontrivial Jordan block on $w^{\perp}$. So I tried making $A$ be of the form $\left( \begin{smallmatrix} 0 & c \\ 0 & 0 \end{smallmatrix} \right)$ in the basis $\begin{pmatrix} 1 & 1 & 0 \end{pmatrix}^T$, $\begin{pmatrix} 0 & 1 & 1 \end{pmatrix}^T$. At first I tried this with $c=1$, but some of the entries came out negative. So I redid it with a smaller value of $c$. (I knew this had to work because, when $c=0$, you get $A = \left( \begin{smallmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{smallmatrix} \right)$ so, by continuity, for $c$ small enough I had to get nonnegative entries. 


Here's a 2parameter family of examples. Let $$A=\pmatrix{a&b&1ab\cr22a3b&3a+4b2&1ab\cr a+3b1&33a5b&2a+2b1\cr}$$ If $a$ and $b$ are chosen so that all the entries are between 0 and 1, then this is a doublystochastic matrix. It has the repeated eigenvalue $3a+3b2$, which is not 1 if $a+b\ne1$. The matrix $A(3a+3b2)I$ has rank 2, provided $a+2b\ne1$. So if $a$ and $b$ are chosen in accordance with the stated conditions, this is a nondiagonalizable doublystochastic matrix. I found this by letting $A(1,1)=a$, $A(1,2)=b$, $A(2,1)=a\lambda$, $A(2,2)=b+\lambda$, letting the other entries be what they have to be to make all row and columnsums 1, and then choosing $\lambda$ to make the trace $1+2\lambda$, so the eigenvalues have to be $\lambda$ repeated and 1. EDIT: If, for some reason, you want the matrix to be singular, then just take $\lambda=0$. Then you get the oneparameter family $$A=\pmatrix{a&(2/3)a&1/3\cr a&(2/3)a&1/3\cr12a&2a(1/3)&1/3\cr}$$ Now if you choose $a=1/4$ you get (essentially) David Speyer's example. 


In complement to David's answer, the eigenvalue $\lambda=1$ of a doubly stochastic matrix $A$ is always semisimple. The matrix is permutationally similar to a block uppertriangular matrix $B$ whose diagonal blocks are irreducible. Because $B$ is doubly stochastic too, the sum of the entries in the uppertriangular blocks equals that of the entries in the lowertriangular blocks. The latter is zero, whereas the former is a sum of nonnegative terms. The uppertriangular part is thus zero: $B$ is block diagonal. Now apply PerronFrobenius to each diagonal block. 

