Shuffling sections of an ordered list based on tuple values
Both branches of the if statement have the line:

temp.append(i)


This duplication could be avoided.
The variable temp could have a better name, for example group or current_group.
i[1] is evaluated twice.
The variable name i is normally used for an index, but in this case it is an element of the list, so it could have a better name.
These lines appear twice:

random.shuffle(temp)
new_pieces_needed +=  temp


This duplication could be avoided by postponing the shuffles until the groups have been found, like this:

# Group pieces_needed according to their frequency.
groups = []
current_freq = object()
for piece in pieces_needed:
    freq = piece[1]
    if freq != current_freq:
        groups.append([])
        current_freq = freq
    groups[-1].append(piece)

# Randomly shuffle each group.
for group in groups:
    random.shuffle(group)

# Concatenate the shuffled groups.
new_pieces_needed = [piece for group in groups for piece in group]

There is something arbitrary about the use of "pieces" and "frequency" and piece[1]. The same general algorithm would work for any kind of data, not just pieces. So I think the code would be clearer if we generalized it like this, taking an arbitrary iterable and an optional key function:

def shuffle_groups(iterable, key=None):
    """Group the iterable (using the key function if supplied), randomly
    shuffle each group, and return the concatenation of the shuffled
    groups.

    """


and then we can shuffle the pieces by passing operator.itemgetter(1) for the key argument:

from operator import itemgetter
new_pieces_needed = shuffle_groups(pieces_needed, key=itemgetter(1))

The grouping logic can be delegated to itertools.groupby and the concatenation to itertools.chain:

from itertools import chain, groupby
from random import shuffle

def shuffle_groups(iterable, key=None):
    """Group the iterable (using the key function if supplied), randomly
    shuffle each group, and return the concatenation of the shuffled
    groups.

    """
    groups = [list(group) for _, group in groupby(iterable, key)]
    for group in groups:
        shuffle(group)
    return list(chain(*groups))