Мне такую бумажку давали еще в марте 2010.

Нет не нужно.

Речь не о бумажке, а о штампе 

Делайте туристическую заранее, о визе по прилету даже не думайте, если хотите на долго прилететь сюда.
Тут собираем ссылки на посты по этой теме, там все описано.

Если там есть консульство, то должны делать 

Да, можно так, это не сложно - билеты в ближайшие страны дешевые, визу можно получить за пару дней.
Есть способы остаться дольше за деньги, многие турагенства с удовольствием сделают все необходимые документы для этого (например, якобы вы работаете или учитесь тут).
Можно вообще отдать паспорт в турагенство и его будут вывозить за границу, ввозить обратно, получать штамп на месяц, продлять еще на один, потом опять вывозить и так далее.

Если вы еще не были на Бали, то не стоит сразу рваться сюда на год или дольше, сначала попробуйте приехать на полгодика, потом начнется сезон жары и дождей, может вам уже и не захочется тут жить, тем более, что рядом куча не менее интересных стран 

Этот способ конечно же не легален, но практикуется одним нашим знакомым уже довольно долго

Точно не знаю, помоему что-то около 150 долларов за раз.

Каждое продление стоит по 250 000 индонезийских рупий. Второе продление стоит 265 000. Итого за 4 продления по месяцу (полгода пребывания в стране) уходит 1 015 000 индонезиских рупий, или попросту 110 долларов (не считая стоимости самой визы).

Хочу уточнить Проверка показала возможность продления еще на месяц?

Нужны ли обратные билеты для получения визы по прибытию?

Судя по сложности получения визы в России, проще будет через 2 месяца выбраться в Тай и сделать там уже человеческую визу.