The gemara said that the zekanim would take those large aravos from motza which were used to overhang the mizbayach as part of their arba minim. Didn't we learn that all of the 4 minim have to be "shelachem" as it says u'lekachtem lachem?
You are correct. The Zekenim indeed acquired the Aravos. Since the Aravos were not actually Kodesh, the Zekenim were able to be Zocheh them.