You might want to check out some of the "pumidors" folks on teachat have made.
I think that cedar and any strong smelling wood is definitely out... it will definitely get into the flavor of the tea in a way that I think most people would call bad. Also, anything you make that's new is probably going to end up with smells from any glue and varnish used. So I think you'd like something that will look nice with very minimal finishing - maybe wengé (not sure if that needs to be oiled, or if the oil would cause problems with the tea cakes).
I know antiques are hard to find over there sometimes, but if you can find one of those Chinese kitchen cabinets, I think that would be perfect (one with the ventilated cabinets on top, and solid doors on the bottom). With something that's already made, you can usually get a good sense if it has a strong smell or not, and older cabinets (at least if they haven't been refinished recently) shouldn't have as strong a smell from varnish or glue, though they might have some weird smells of their own. I have heard (though I have no personal experience) that putting the cabinet outside in direct sunlight for a little while can help get the odors out, and leaving it closed up for a week or two with some bamboo charcoal and some cheap shu might be a good idea also.
What I do is store the pu'er in a big closet in the back of my appartment (along with some other stuff). It's mostly sheng, but I have a separate shelf for the one or two shu cakes I have. I stack similar years (+- 4-5 years) together; if I have enough of a particular region within that time period, I'll stack similar regions together. I keep the door closed most of the time; I crack the door every once in a while to let some air (and humidity) in, especially when it's nice and humid out, then I shut it and put a towel across the floor. The nice thing is that the closet tends to even out fluctuations in temperature and humidity somewhat. Because the closet is so big, putting a pan of water inside doesn't seem to help humidify it much; I'm guessing in your case, that's not too much of a concern.
I have a Japanese tea tansu made from Zelkova wood. Don't currently store any pu in there, but the bottom stores most of my sealed canisters of other teas, and the top holds my teapots. When I bought it, it didn't seem to have that strong of a smell, but the smell actually is pretty strong, and I am a little worried about the smell being absorbed by my teapots. I have bamboo charcoal stuck all around (btw, I've heard you need to refresh bamboo charcoal by putting it in direct sunlight every once in a while), but so far it hasn't made that much difference. The bottom part is starting to pick up a little tea smell, though, at least.