It's going to be very difficult for the Minotaur to be self-reliant. As you state, this maze is not a very good place to grow food.
So here's how you do it:
Jurassic Park Style
Have a narrow, vertical shaft leading down into the heart of the maze (its existence can be a closely guarded secret). Lower chunks of meat in for the Minotaur to feed on.
Only One Entrance
Alternatively, if you really want a single way in/out simply lead animals such as sheep or cows into the labyrinth a little way, and run out.
If you don't want to risk even stepping foot inside then rig up a pulley system (anchored inside the labyrinth) and pull the animals in from the outside.
All you'd need is a long loop of chain and a ring firmly affixed in the wall of the labyrinth. You tie the animal to the chain and pull, leading it inside. Once the Minotaur rips the animal off the chain you can cycle it through the ring and pull in the next one. (you could potentially have to fix the ring/chain every once in a while, but the Minotaur would probably let you, or even help you do it)
Alternate Food Source
Another way to provide the Minotaur with food is to have animals stumble into the labyrinth through some sort of natural cave system. It would make the food source unreliable/hit and miss, but it would be a lot more realistic than having your fearsome murder-pet lick lichen off the walls.
Rat Burgers
Realistically the Minotaur won't be able to sustain itself unless it's quite intelligent and resourceful. However, assuming that you really want a hands-off approach then it would probably set up traps for the many pests roaming the underground tunnels.
Eventually it can even start breeding rats or other pests for a food source.
You Should Feed It
If you are the one feeding this thing then you have leverage over it. It has a reason to at least pretend to obey you.
You also have some very real power over it. If it becomes too rebellious you cut its food rations and discipline it. If it tries to attack you, or goes berserk simply withhold all food and watch it slowly starve to death.
A self reliant Minotaur is not stuck inside the maze - it's in charge of a maze you can't get it out of.