I'll first describe what I think makes this a difficult problem and then give an algorithm that quite significantly reduces the number of permutations you have to handle, though not to one per orbit.
The problem can be viewed as finding all equivalence classes of Young tableaux under two different types of operations. On the one hand, we can permute rows of equal length and cyclically permute the entries in a row; an equivalence class under these operations corresponds to a permutation. On the other hand, we can permute the numbers in the boxes according to the elements of $C_\pi$, which is generated by permutations of the cycles of $\pi$ and cyclical permutations of the elements of a cycle of $\pi$; an equivalence class under these operations corresponds to an orbit under conjugation by $C_\pi$.
We can view these two types of operations as symmetry operations of two tableaux: one for the permutation being built and one for $\pi$. What makes the problem difficult is that these two types of operations interact in a complicated way. If we only had to deal with one of them at a time, we could easily define a canonical representative of each equivalence class by using the permutations to enforce appropriate ordering conditions; an efficient algorithm would then consist in filling in the boxes one by one, at each step only trying out the possibilities that are compatible with the canonicity conditions.
I haven't been able to find a canonical form for both types of operations at once such that it would be straightforward to check whether a partially constructed permutation may still end up as a canonical form. The best I was able to do was to enforce canonicity fully for one of the types and partially for the other; however, this already substantially reduces the number of permutations that need to be generated.
This raises the question for which of the types of operations canonicity should be fully enforced. If it's fully enforced for the first type, corresponding to the symmetries of the tableau for the permutation being generated, then we generate every permutation only once, but we may generate several representatives for an orbit. If it's fully enforced for the second type, corresponding to the symmetries of the tableau for $\pi$, then we generate only one representative per orbit, but we may generate it several times.
In the first case, we need to add a step in the end that canonicalizes the permutations with respect to the second type of operations to make sure we keep only one representative per orbit; whereas in the second case we just have to check whether we've already produced a given permutation. Since that's a bit easier, I'll describe an algorithm that uses the second option (full canonicity for the second type of operations); once you've seen this one, it will be relatively straightforward to formulate the other one if you so prefer. (Which of these two options eliminates more redundancy will probably depend on $\pi$, possibly in a complicated way; it might be a question best decided by empirical tests which option would be more efficient for your intended application.)
Find the cycle structure of $\pi$, and consider its Young diagram $Y_\pi$. Loop over all partitions of $n$ (for instance Section 7.2.1.4 of The Art of Computer Programming shows how to do that), and for each partition $p$, consider the corresponding Young diagram $Y_p$. We want to assign the boxes of $Y_p$ to the boxes of $Y_\pi$ in all possible ways. To enforce canonicity with respect to $Y_\pi$, we assign the boxes of $Y_p$ one by one, traversing $Y_p$ row by row from top to bottom and from left to right; in each step, we may assign the next box $a$ of $Y_p$ to a box $b$ of $Y_\pi$ only if the first box in the row containing $b$ has already been used or if $b$ is the first box in its row and all first boxes in the rows of equal length above it have already been used. We loop over all possibilities that fulfill this condition and for each such possibility $b$ we assign $a$ to $b$ and make a recursive call to assign the next box. This ensures that we generate exactly one out of all assignments related by the symmetry operations of $Y_\pi$, that is, we generate only one representative for each orbit.
Now we want to try to generate each representative as few times as possible; that is, we want to enforce canonicity with respect to $Y_p$ as much as possible. Consider the assignment of an entire row $r$ of $Y_p$. Since we can cyclically permute the boxes of that row, we can transform some assignments into each other. At first one might think (and my first, incorrect answer rested on that assumption) that we always only have to consider the assignment where the first box of $r$ is assigned to the least box (according to some fixed order $\omega$) in $Y_\pi$, since otherwise we can cyclically permute $r$ to make it so. However, this is not quite true, since this may be in conflict with the canonicity conditions for $Y_\pi$. For instance, if $r$ has three boxes $r_1, r_2, r_3$ and we assigned $r_1$ to the first box $s_1$ of a row $s$ in $Y_\pi$, $r_2$ to some box lesser in $\omega$, and then $r_3$ to the second box $s_2$ of $s$, we can't cyclically permute the boxes of $r$ such that $r_1$ takes the place of $r_2$ (as it should), since that would make $r_2$ take the place of $r_3$ and $r_3$ take the place of $r_1$, resulting in an assignment of $r_3$ to $s_1$ and $r_2$ to $s_2$, which violates the canonicity conditions for $Y_\pi$.
However, as you can see from the example, this problem can only occur if we assign boxes of $Y_p$ to boxes of $Y_\pi$ that must be filled in a particular order relative to each other, that is, either to the first box in a row and another box in that row, or to two first boxes of rows of equal length. For large $n$, most possible assignments will not lead to such a collision, and in these cases we really do only have to try the one assignment that ensures canonicity with respect to $Y_p$.
To apply this in the above algorithm, whenever you assign the last box of a row $r$ of $Y_p$, find the least box $b$ (according to $\omega$) of the boxes that the boxes of $r$ are assigned to, and check whether there is any cyclical permutation of the boxes of $r$ that causes a box of $r$ further to the left to be assigned to $b$ and that doesn't violate the canonicity conditions for $Y_\pi$. If there is, that means we'll reach that permuted assignment at some other stage of the algorithm, so we can skip it now. If there isn't (in particular, if the first box of $r$ is already assigned to $b$), use the unaltered assignment.
This takes care of the cyclical permutations of the rows of $Y_p$. We can deal with the permutations of rows of $Y_p$ of equal length in a similar way. To do so, whenever you assign the last box of a row $r$ of $Y_p$, after checking that the assignment shouldn't be skipped because of a cyclical permutation of $r$ as described above, check whether $r$ has other rows of equal length above it. If so, check whether the first box of $r$ is assigned to a lesser box (according to $\omega$) than all the other first boxes of rows of $Y_p$ of equal length. If so, use the assignment. If not, check whether you can exchange $r$ with any row above it of equal length whose first box is assigned to a lesser box than the first box of $r$ without violating the canonicity conditions for $Y_\pi$. If so, skip the assignment, since we'll reach it with those rows exchanged at another stage of the algorithm. If not, use the unaltered assignment.
It remains to describe what to do when you've reached the last stage of the recursion and successfully assigned the last box of $Y_p$ ("successfully" meaning that you've passed the skip tests and would now make a recursive call to assign the next box if there were one). You now have a full assignment of the boxes of $Y_p$ to those of $Y_\pi$ that fulfills the canonicity conditions for $Y_\pi$ and may yield a new representative. To construct that representative, use some fixed Young tableau $T_\pi$ corresponding to $\pi$ (any of the equivalent ones will do, but it must be the same one throughout) and fill the boxes of $Y_p$ with the numbers which the boxes they're assigned to in $Y_\pi$ contain in $T_\pi$ (which has shape $Y_\pi$.) Then read off the permutation represented by the resulting Young tableau $T_p$ (which has shape $Y_p$), check whether it's been generated before, and if not, add it to the set of representatives.
I hope a) I haven't made any unwarranted assumptions this time and b) I've at least somewhat succeeded in describing the algorithm such that you can implement it. Let me know if you'd be interested in an implementation in Java.
