What is the idiomatic Rust way to copy/clone a vector in a parameterized function?

Your attempt #1 is almost correct, you just have to move to_owned() to the first line:

fn shuffle<T>(vec: &mut [T]) {
    // ...
}

fn shuffle_create_new<T: Clone>(vec: &[T]) -> Vec<T> {
    let mut newvec = vec.to_vec();
    shuffle(&mut newvec);
    newvec
}

This happens because calling clone() on a slice will return you a slice (i.e. &[T]), and you cannot go from &[T] to &mut [T] because you cannot choose mutability of a reference (borrowed pointer). When you call to_owned(), however, you are getting a fresh instance of Vec<T> and you can put it into a mutable variable to get mutable vector.

As of Rust 1.0, either slice::to_vec or to_owned() method from the ToOwned trait can be used to create Vec<T> from &[T].

There are also now several ways to obtain &mut [T] from Vec<T>: the slicing notation (&mut vec[..]), the deref conversion (&mut *vec) or the direct method call (vec.as_mut_slice(), though this one is deprecated):