I think -- and this is mere speculation on my part, mind you -- that most of the wooden debris is from artifacts and buildings that the humans had made before their extinction and before the robots took over. Plus, since MetroMind relies so much on scavenging, it is possible that wood ends up being reused when building new things as well, as long as it is recovered from something that is no longer working or no longer serves its purpose.
As for the lack of trees, well, the whole area was the setting of a huge war that used nuclear bombs and other means of mass destruction, including giant robots and deadly viruses, so, it's quite likely some combination of those -- or all of them -- destroyed all trees and rendered the land sterile. Also, most of the landscape seems to be an immense junkyard constantly being looted and raided, which doesn't exactly allow for the growth of trees. Something robots don't exactly need, since they don't need to breathe (I assume).
Yeah, the environment was basically rendered unsuitable to life in general.
There's really no good explanation for the wood: Vic liked it from a visual standpoint, probably without considering the question where it came from. That said, I think at some point there might've been a quip somewhere suggesting it wasn't really wood but was some kind of synthetic polymer. Can't remember.
Sorry there's not a great answer!