Загранпаспорт нужен. И всё. Поедете из Владика, не сразу суйтесь в Тбилиси, сделайте остановку на денек в Казбеги (Степанцминда), слазьте на гору к Гергети Цминда Самеба, погуляйте по ближайшим ущельям, посидите у Терека. В Тбилиси оттуда постоянно ходят дешевые маршрутки, да и вообще, трафик достаточный.
Тбилиси - это минимум два дня, а лучше и побольше, там бродить по улочкам не устаешь, а есть еще и серные бани, и Нарикала, и фуникулерчик к телевышке, где в детском парке замечательный ресторанчик с вкуснейшим лохи кинзмари. Дальше по Грузии? Это смотря, что Вы хотите от этой страны. Я бы предложил Мцхета с ее комплексом Светицховели и Джварским монастырем на стрелке Арагви и Куры, там можно поесть вкуснейшего лобио и хинкали в культовом Салобио, потом рвануть на электричке в Боржоми - причаститься божественного нектара, искупаться в горячем источнике, прокатиться узкоколейкой в Бакуриани по красивым горным ущельям. Там же, в Боржоми, можно выцепить транспорт в Вардзиа (там лучше ночевать, чтобы пещерный город смотреть без зевак-туристов). Кстати, из Боржоми туда нередки экскурсии, и можно к одной из них халявно присоединиться - спросите в инфоцентре.
Из Бакуриани я б выехал в направлении Кутаиси, денек полазил бы там, ну и напоследок направился бы в сторону Батуми - посмотреть новую Грузию, искупаться в море (не скажу за апрель, но вот 1 мая я там купался, вода была теплой), попить турецкий кофе. В Батуми - учтите - всё довольно дорого, и вообще, по крайней мере, в центре, он мне напомнил какой-то европейский город, итальянский, что ли.
Армения? - не знаю, я не ездил, но вот, если замените ее Азербайджаном, то по пути к Баку будет симпатичнейший городок (хотя многие плюются - новострой. Но такой классный новострой) Сигнахи, монастырский комплекс Давид Гареджа, а уже на территории соседней страны можно заехать, например, в Шеки.