As I understand the trains start riding in around 05:00, and if leaving yeoksam station, it would take 1.5 hours to get to the airport, meaning I will arrive one hour before my flight. Is that too close? What other ways are there except the subway?
The first AREX airport express from Seoul station leaves at 6:00 AM, arriving at 6:43. The service is reliable and ICN is a very efficient airport, so this should be plenty of time to check in for your flight and go through security.
Your issue will be getting from Yeoksam to Seoul station, because this is too early for the subway. Google Maps suggests bus 463 (dep 5:25, arr 5:49), but I would probably just cab it.
I think this is the best way, limousine bus #6020 Pretty cheap and direct from where I need to the airport. http://www.seoulbus.co.kr/eng/index/airportbus_01_1.php?val=11