They did chop trees with stone tools. Here you can see how:
Even felling big trees doesn't need iron tools - controlled fire will do most of the work: http://www.cherokeeheritage.org/attractions/dugout-canoe/
https://youtu.be/zVPUFMwm73Y?t=228
Relevant: Coppice