You'd need to replace wood in 2 ways:
- As a construction material
- As an energy source
If I understand the question correctly, you're saying "Given abundant resources of coal and any metals or other needed materials" but you don't mean that said materials are lying about, just that they exist. In other words, I'm assuming said humans still need to mine ores and coal.
Finding other construction materials may not be that hard - there's bone for small projects, although it isn't as easy to shape and you can't get it in quantities that are easy to work with when you need to make something solid.
The obvious other choice is stones - which were used a lot, but were also abandoned pretty quickly. Stones are hard to work with, heavy and you can't easily form arbitrary shapes from them (a stone sword, for instance, is hard to craft without getting rid of most of the stone - not that it's a practical thing to make anyway, but thin, long objects are a lot easier to make with wood than stone).
If these humans where given enough time, I guess they could do pretty well with just these - it would take the more time, due to the added difficulty, but they might be making pretty advanced constructs eventually.
edit - Zibbobz suggests that clay could be used as a construction material (including making ovens).
This is tougher. Coal requires mining implements (unless you find it loose, which isn't going to be common) and was usually created in large amounts from wood, which is out of the picture. So all you get is coal ore. Oil is generally going to be too deep to get and not easy to refine (although you might not need to refine it per se, at an early stage). I'd say they'd need to find another source, before getting to coal, but once they get there, it may serve as a replacement for wood (maybe not for home fires though).
Burning dried shrubbery might allow the creation of fires, although it would be very inefficient - huge quantities would be needed, probably compressed to make log equivalents.
There's other minerals such as nitre which, if your humans are amazing at getting the energy out of things, might be able to use without blowing up (doubtful).
Cheap fuel seems to be gone unless you have some form of composing biological fuels - maybe some form of composting would help.
edit - TimB adds that peat would probably be the best fuel source in this case - Stendika also suggested that dry animal dung (apparently also known as 'buffalo chips' which I wasn't aware of) could be used as a fuel. superluminary reminds that animal fat can also be used, such as in candles.
Metals really don't come into this picture in my opinion - you need tools to extract them, unless you find small quantities lying around and while they can serve as a construction material, that's only after you've been able to find the tougher ones in large enough quantities. Metals only serve as an energy source with modern technology and even then, only in quite specific and high-tech situations.