The airport's current capacity is 44M/year, and total passenger number was 35M in 2011, and it will be like 38M in 2012. By 2017, when the third phase opens, the capacity will go up to 62M. Although the passenger number is quickly reaching the capacity (44M), this airport is busy only on certain peak times, and runway usage is well below 60% of available slots. (So no additional runway on the 3rd stage)

KE's concourse arrivals are more or less due to not efficient use of gates (wrong airline distribution), and not due to lack of capacity. Since both KE and OZ use the same terminal, and since both airlines have same peak hours, main terminal becomes crazy on those times. If they were mixed with foreign airlines, which has different peak times (or no peak hours at all), the problem would have been solved.

By the way, I don't think they decided which airlines (or alliances) will used the new terminal. Both KE and OZ wants to go there, and it's still undecided, despite of your source. Either KE+skyteam or OZ+star will move to there, and the other alliance will leave (or move) on the main terminal. Since KE+skyteam is larger at ICN, I expect the new terminal will be skyteam's. The others (and oneworld) might use concourse A.