I would have thought that a drawer might be the easiest way.
I assume that you are not intending to make this truly vandal-proof but rather a treat-dispenser for kids that will take only mild abuse. If so, then a stack of either chocolate bars or small candy pieces above a small drawer would allow one bar or one portion of candy to be withdrawn. The drawer would be indented into a flat material so that the piece behind it would support the stack when the draw was pulled out. When the drawer is returned empty, the stack falls by one place and fills the drawer for the next dispensation.
You would want some sort of spring-bolt to hold the drawer, which you could withdraw using a solenoid controlled via a transistor from your arduino. I guess you would also have some way of sensing that a treat was due, so you will want some sort of "coin" detector. How sophisticated that will be may depend on how "real" your project is.