Thank you all for the meta discussion. I know we sidetracked a bit but please everyone remember, this is an open discussion floor.
I can present you a use case, just didnt think I even needed one. This seems so obvious to me that it should just go in without much saying. In the project I maintain (construct) there are declarative testcases that look like a long list of (func, args, excepted output, error type) tuples. There is no way for me to call shuffle in there. I can only use shuffled. So here it is, the use case you requested.
The argument that it can be easily implemented does not stick. In interactive sessions, indeed writing own functions is a pain in the ass. Expecting batteries included is rightful. Builtins like min() max() sum() are sooo easy to implement on your own. So are some methods in itertools, you can even find their sources in the docs. That doesnt mean batteries should not be included.
shuffled = sorted(list, key=lambda x: randint) This is wrong because sorting is comparison based and must be nlogn bound. Shuffling is cheaper computationally. Also someone would have to come up with a formal proof that it provides a uniform distribution which probably was done for the shuffle implementaion.
Another argument still remains: there is a missing analogy between sort-sorted and shuffle-shuffled.
I did NOT suggest making it a builtin. It should be added to random module.
"Also shuffle() should return self so mutating methods could be chained."
That was a side suggestion. I withdraw that part. Chaining methods is sometimes useful but we can go without it.
pozdrawiam, Arkadiusz Bulski