My concern here, though, is beds. While modding milk as a fermentable item makes sense, we need stone and/or metal beds. Also, bins are right out, unless you want your poor dorfs trying to haul around copper bins. I'll have to doublecheck if you can make metal wheelbarrows, but those may be out too.
I would recommend the allowance and usage of logs only in those cases where the tree must be removed due to pathing problems, particularly towards the anti-vegan idea of the challenge. It's quite possible to end up with trees blocking depot access and/or maneuvers in the caverns, though most can be mined around except in the case of narrow walkways between water.
If the challenge is to be a true anti-vegan, then logs would absolutely outlawed. The single exception would be where trees would need to be removed, as you noted, in which case they would immediately be disposed of in an appropriately inflammatory fashion.
Regarding beds... this, I think, is the true challenge. While mead is an existing, albeit limited alternative to plant-based alcohols that already exists in the unmodded game, there is no alternative to wood for the construction of beds. Assuming that whoever attempts this challenge uses the unmodded game - which is, to be sure, much more challenging than the alternative - the only beds will come from the lucky few strange moods. These beds would obviously be afforded to the few noblery, while the vast masses of the fortress sleep on cold stone floors and are placated by vast amounts of masterwork statues and high-quality meat-based prepared meals.
Regarding strange moods, if one were to go true anti-vegan, all carpenters and woodcrafters who mooded, as well as any others who required logs or plant-based cloth for their artifacts, would go insane do to the restriction. Any overseer attempting this challenge - or, at least, this extremely restricted version of it - would have to be prepared for these eventualities.