I think a cool idea would be that some mobs have the ability to break down certain blocks like wood or stone or something. Give mobs an axe or a hammer that can break through stone in 4 or 5 hits. This could be put into the hard difficulty because I imagine this would be quite stressful for new players.
Please search, and find the "Zombie Improvement" thread.