Thanks for the answers! The reason I was confused (in addition to my obvious lack of knowledge in group and graph theory) was this short discussion on stack exchange:
https://math.stackexchange.com/questions/3270801/cyclic-and-circular-permutation-are-they-different-concepts
Considering people around a table, I am not looking for the (n-1)! possible ways of ordering n people, but rather the much simpler n shifts where there is an initial fixed ordering of the people.
So randperm will not do i am afraid. But stumbling over the circshift function, I seem to have resolved my problems:
julia> rand_circshift(array::AbstractArray) = circshift(array, rand(1:length(array)))
rand_circshift (generic function with 1 method)
julia> rand_circshift(n::Int) = rand_circshift(1:n)
rand_circshift (generic function with 2 methods)
julia> Set([rand_circshift(3) for _ in 1:10000])
Set{Array{Int64,1}} with 3 elements:
[3, 1, 2]
[2, 3, 1]
[1, 2, 3]