Here is a Python implementation of the idea #2:

from itertools import tee
def groupby(iterable, key=None):
    if key is None:
        key = lambda x: x
    def grouper(currvalue, it, tgtkey):
        yield currvalue
        for currvalue in it:
            if key(currvalue) != tgtkey:
                break
            yield currvalue
    it = iter(iterable)
    tgtkey = init = object()
    while True:
        try:
            currvalue = next(it)
        except StopIteration:
            return
        currkey = key(currvalue)
        if tgtkey is init or currkey != tgtkey:
            tgtkey = currkey
            it, it2 = tee(it)
            yield (currkey, grouper(currvalue, it2, tgtkey))