Whereabouts are you? That'll make a big difference to what perennials are suitable. Fruit trees definitely a good idea, also nuts. Don't know how big the space is but you could maybe grow things to provide a yield other than food, like fuel and/or weaving/building materials.
You could also grow things for biomass/compost, eg. Comfrey, so it wouldn't matter if the dogs shred it you can rake up the leaves and use them (and comfrey will survive that).
Don't know if this would work, but you could maybe grow some vining crops, like squash, by making a sturdy pyramid/teepee shaped trellis structure. The seeds/seedlings could be planted inside the structure where they'd be safe from dogs, and the plants would grow up out of harms way. Just a thought:)