In order to shuffle the sequence uniformly, random.shuffle() needs to know how long the input is. A generator cannot provide this; you have to materialize it into a list:

lst = list(yielding(x))
random.shuffle(lst)
for i in lst:
    print i

You could, instead, use sorted() with random.random() as the key:

for i in sorted(yielding(x), key=lambda k: random.random()):
    print(i)

but since this also produces a list, there is little point in going this route.

Demo:

>>> import random
>>> x = [1,2,3,4,5,6,7,8,9]
>>> sorted(iter(x), key=lambda k: random.random())
[9, 7, 3, 2, 5, 4, 6, 1, 8]

While I do agree with others that Solution 2 is more readable with some improvements, there are also a few improvements that can be done on Solution 1.

• It is unnecessary to construct lists from iterables (e.g., generator expressions) when all that is needed is an iterable. For example,

  _args      = [arg if type(arg)!=dict else arg.items() for arg in args]
  args_split = [arg for arg in zip(*_args)]
  

  Here, the unpacking operator * works on arbitrary iterables. So one can just do

  _args      = (arg if type(arg)!=dict else arg.items() for arg in args)
  args_split = [arg for arg in zip(*_args)]
  

  The parantheses keep the generator expressions without actually materializing them into lists.

• It is better to use isinstance(arg, cls) rather than type(arg) == cls

• Unpacking an iterable into a list can be done using list(iterable), which is more efficient than a list comprehension [arg for arg in iterable] that uses an explicit for-loop.

• This expression

  args_types[i for i, arg in enumerate(args_shuffled)]
  

  can be rewritten using zip to avoid the need of indices:

  [cls(arg) for cls, arg in zip(args_types, args_shuffled)]
  

Following is an improved version of Solution 1

def ordered_shuffle(*args):
    arg_types = map(type, args)
    arg_elements = (arg.items() if isinstance(arg, dict) else arg for arg in args)
    zipped_args = list(zip(*arg_elements))
    random.shuffle(zipped_args)
    return [cls(elements) for cls, elements in zip(arg_types, zip(*zipped_args))]

Generator endlessly shuffling and yielding:

def endless_shuffling(iterable):
    values = list(iterable)
    while True:
        random.shuffle(values)
        yield from values

Instead of your iter(all_angles), use endless_shuffling(all_angles) (and remove your own other shuffling).

One way to then get your list:

random_angles = endless_shuffling(range(-180, 180))
n_list = list(islice(random_angles, 1000))

If you give it an empty iterable and ask it for a value, it'll "hang", so either don't do that or guard against that case (e.g., with an extra if values: or with while values:).

I also tried a faster way to iterate than sending every value through a generator, but the shuffling dominates so it doesn't make a big difference:

with shuffling:
448.3 ms  endless_shuffling1
426.7 ms  endless_shuffling2

without shuffling:
 26.4 ms  endless_shuffling1
  5.1 ms  endless_shuffling2

Full code (Try it online!):

from random import shuffle
from itertools import chain, islice
from timeit import default_timer as time

def endless_shuffling1(iterable):
    values = list(iterable)
    while True:
        shuffle(values)
        yield from values

def endless_shuffling2(iterable):
    values = list(iterable)
    return chain.from_iterable(iter(
        lambda: shuffle(values) or values,
        []
    ))

funcs = endless_shuffling1, endless_shuffling2

for f in funcs:
    print(*islice(f('abc'), 21))

for i in range(6):
    for f in funcs:
        t0 = time()
        next(islice(f(range(-180,180)), 999999, 1000000))
        print('%5.1f ms ' % ((time() - t0) * 1e3), f.__name__)
    print()
    if i == 2:
        print('without shuffling:\n')
        def shuffle(x):
            pass

random.shuffle should work. Here's an example, where the objects are lists:

from random import shuffle

x = [[i] for i in range(10)]
shuffle(x)
print(x)

# print(x)  gives  [[9], [2], [7], [0], [4], [5], [3], [1], [8], [6]]

Note that shuffle works in place, and returns None.

More generally in Python, mutable objects can be passed into functions, and when a function mutates those objects, the standard is to return None (rather than, say, the mutated object).

As the documentation explains:

The functions supplied by this module are actually bound methods of a hidden instance of the random.Random class. You can instantiate your own instances of Random to get generators that don’t share state.

So, you can just create your own random.Random instance, with its own seed, which will not affect the global functions at all:

>>> import random
>>> x = [1, 2, 3, 4, 5, 6]
>>> random.Random(4).shuffle(x)
>>> x
[4, 6, 5, 1, 3, 2]
>>> x = [1, 2, 3, 4, 5, 6]
>>> random.Random(4).shuffle(x)
>>> x
[4, 6, 5, 1, 3, 2]

(You can also keep around the Random instance and re-seed it instead of creating new ones over and over; there's not too much difference.)