Does this shuffle have non-zero probability for all permutations?
Yes. Your algorithm can return all permutations.
You can prove it by fixing any arbitrary permutation $\pi$ of the input string str and showing by induction that, after the $i$-th iteration of the outer loop, the first $i$ characters of str can match the last $i$ characters of $\pi$. 

For $i=0$ this is trivial. 
For $i&gt;0$: Let $n$ be the lenght of str, $x$ be the character in position $1+n-i$ of $\pi$ (indexing positions from $1$), and $j$ be the index of the first occurrence of character $x$ in str with the additional constraint that $j \ge i$ (this index always exists by induction hypothesis). A string temp that will satisfy the induction thesis (as it will be assigned to str) can be found as follows: 


copy the first $j-1$ characters from str to temp (by appending them to temp). In particular this copies the first $i-1$ characters of str which, by induction hypothesis, match the last $i-1$ characters of $\pi$.
prepend the $j$-th character of $x$ of str to temp.
append the remaining $n-j$ characters of str to temp.