I agree with Tyler on the fencing. Deer will eat off everything before It can even get started. They don't wait for things to get big
enough to be more than a nibble. And it's got to be a tight enough gate, that has a way to close automatically; just one day leaving the gate open can wipe out young trees and shrubs. (deer got into my
yard just once and killed my young pear trees and apples). Unless there is lots of natural vegetation in areas away from the garden, the wild things will zoom right in on it.
Most of the lilac bushes and wild roses and other shrubs in this town are completely deer-pruned outside the fences, up to out of a deer's reach. And they can reach pretty high up, raising up on their hind legs or on a
fence etc. They haven't eaten my hollyhocks or daffodils, outside the fence, but think tulips and fruit trees are candy, in essence. Unless you plant things deer don't find palatable, nothing will survive long enough to be large enough to make a difference, in my opinion.
I know
Toby Hemenway, in the first edition of
Gaia's garden, talked about a deer-defeating hedge, but a few years ago I saw where he posted something on the net that he had found the deer just pushed past the stuff they didn't like to get to the good stuff. So I think one would have to at least start with a fence, and maybe grow stuff near the fence to eventually replace it.