Как повысить эффективность кода? Или такое поведение программы считается нормальным?
Наиболее быстрый алгоритм:from random import random

while True:
    try:
        total = int(raw_input('\nВведите количество бросков: '))
    except ValueError:
        print 'Введено некорректное значение: ожидается целое число.'
    else:
        # side1 = sum(random() < 0.5 for n in xrange(total))
        side1 = int(round(sum(random() for n in xrange(total))))  # эквивалент random() >= 0.5
        side2 = max(0, total) - side1
        print 'Результат: орёл - {0}, решка - {1}'.format(side1, side2)
    finally:
        if raw_input('\nПопробовать ещё раз (Y)? ').upper() != 'Y':
            break
Ещё вариант:import collections, random

options = ('орёл', 'решка')

while True:
    stats = collections.Counter(dict.fromkeys(options, 0))
    try:
        stats.update(
            random.choice(options) for test in xrange(
                input('\nВведите количество бросков: ')
            )
        )
    except:
        print 'Введено некорректное значение: ожидается целое число.'
    else:
        print 'Результат: {0} - {{{0}}}, {1} - {{{1}}}'.format(*options).format(**stats)
    finally:
        if raw_input('\nПопробовать ещё раз (Y)? ').upper() != 'Y':
            break
Замеры скорости:>>> timeit('choice((0,1))', setup='from random import random, choice', number=10**6)
1.4363103769230747
>>> timeit('random() < 0.5', setup='from random import random, choice', number=10**6)
0.18878976080804932
0) Вас не смущает, что Вы используете заведомо равномерное (uniform) распределение, о котором говорится во вступительном абзаце к модулю random?
1) Про русский язык уже написали. Кроме того, зачем смешивать английские слова (times) с транслитом (monetka)? Пишите всё на английском.
2) input() уже конвертирует значение из строки. Если число нецелое (float), то int() отработает без ошибок: int(3.14) = 3
3) Странная структура программы. Не надо делать вложенную структуру (почему цикл бросков монеты идёт под else?), используйте break и continue, чтобы код был более плоским. "Плоское лучше, чем вложенное".
4) В цикле броско монеты операторы "count += 1" и "times -= 1" следует вынести из блока if..elif, чтобы не дублировать оди и тот же код, который всё равно должен выполниться.
5) Если не выпал орёл, то проверять условие var == 'решка' не нужно, достаточно простого else. Там кроме решки больше ничего быть не может.
6) Какая версия Python? 2.x или 3.x? Про целочисленное деление помните?
7) Дальше у меня сломался моск...
Выбрасывай в мусорку всё. Сразу.
Это не рефакторить надо, а переписывать заново.