I would like to rent a car in Yerevan airport, drive it through Armenia, go to Georgia and leave the car in Tbilisi.
Are there any companies who offer that kind of service?
From my experience I will like to advise you NANIKO car rental in Armenia. You can rent a car in Yerevan and leave it in Tbilisi. Also as I compared early (5 month ago) NANIKO was cheapest, so highly recommended.
I used the service of the Armenian car rental company: http://caravan.am/
I paid them to bring a Lada Niva to Tbilisi. From where I would drive in Georgia and Armenia. At the end I brought the car back to their office in Yerevan.
They provided me with the required car documents to cross the border myself from Georgia to Armenia.