The "Brains" Trope:
As far as I know, the idea that zombies eat brains specifically and/or exclusively has its origins in the spoof/ripoff series Return of the Living Dead, which most zombie fans tend to either ignore or treat as the silly nonsense it is. Some zombie fanatics enjoy the series; others, like myself, despise it. In any case, the "official" zombie rules don't subscribe to the idea of brains being a zombie delicacy, although they would be as happy to eat fresh brains as any other kind of fresh meat.
To put it bluntly, zombie digestion doesn't exist. Zombies are, after all, dead. They are compelled to bite any animal that moves, including humans, and given the chance, they will "eat" flesh, but it doesn't actually benefit them in any way. This is a pretty consistent rule across the slow zombie spectrum; it is left unsaid in the classic 1968 Romero film Night of the Living Dead, but Romero gradually built upon the very vague and unspoken rules implied in NotLD, developing them into more concrete concepts in the sequels, like Dawn of the Dead, Day of the Dead, etc, until they were adopted by other writers, filmmakers, and enthusiasts.
However, it is important to note that the name "Romero Zombie Rules" is something of a misnomer, because Romero has never explicitly stated these rules, nor has he even condoned them; in fact, after the original NotLD, Romero has devoted his career to making zombie movies that break the rules bearing his name. As a zombie purist, I have no use for anything Romero has done since Dawn of the Dead, and even that is a poor follow up to Night of the Living Dead, which is almost universally recognized as the best zombie movie ever made.
As Romero slowly but steadily drifted away from the concept he had created, others stepped in to expand on the original idea and explain it in minute detail. The canonical "slow zombie" (also known as the Romero zombie) that we see today in franchises like The Walking Dead and the Max Brooks books World War Z and The Zombie Survival Guide were first envisioned by Romero, but they now owe more to Brooks than anyone else.
Why Do Zombies Do What They Do?
Max Brooks has provided us with the most comprehensive and convincing explanation of zombie physiology and behavior. His ideas have been borrowed by Robert Kirkman (creator of *The Walking Dead), Simon Pegg (Shaun of the Dead), and many others. The initial cause of the zombie pandemic varies from one source to the next, but in every other regard, the concepts are usually almost identical. For our purposes, we will have to ignore the unique twist introduced to the zombie genre by The Walking Dead - namely, the idea that everyone on the planet is already infected, and anyone who dies with their brains intact will become a zombie. We'll be focusing on the basic principle of bite = infection = death = reanimation as a zombie.
Brooks attributes the zombie condition to a virus called Solanum. He has described the virus in exquisite detail, but we can gloss over most of this and focus on the issue you have addressed in your question: biting, eating, and digestion.
To properly understand zombie behavior, you have to remember that zombies aren't people, or any other kind of animal. Zombies are vehicles for a pathogen (usually a virus). The rotting corpse shambling around and attacking people is basically like a car being driven by the virus. The person whose corpse has become a zombie is long gone, never to be seen again. The corpse has no thoughts, no feelings, no needs. It is just the virus' way of getting around and spreading itself to new host organisms.
The virus has to work with the tools at its disposal, which means that it reactivates part of the brain, but only the most primitive portions of the brain, and only the portions that will directly benefit it. The areas of the brain targeted by the virus are as follows:
The motor cortex: The virus needs a mobile host, so it makes sure that the zombie will be able to move around, grab things, and bite things.
The sensory cortex: The virus' only purpose is to infect other hosts, so it needs to make sure that the zombie can see, hear, and smell its prey.
The hypothalamus: The virus needs to make a dead body want to eat every living thing it sees, so it reactivates the hypothalamus, which is responsible for the sensation of hunger. Thus, the only feeling that might be present in a zombie is hunger, although this feeling does not correspond to conscious thought or problem solving as it would in a living person. The zombie doesn't actually think "I'm hungry, I should eat something"; it simply feels hunger.
These are all very primitive functions, and they don't require any conscious thought. But the virus still needs to make sure that its manipulations have the desired effect.
Remember, zombies aren't like us. If you get hungry, you eat until you aren't hungry anymore. The virus doesn't want its zombie host to get full and stop biting people, so it flips the hypothalamus' hunger switch to "On" and leaves it there. Zombies can't get full. No matter how much they eat, their hunger never dissipates.
In his book World War Z, Brooks describes zombies who have eaten so much flesh that their stomachs rupture, splitting the abdomen open and causing the already eaten flesh to spill out onto the floor. The zombie in question sees the meat that has just fallen out of his gut, and eats it again. It falls out again, and the zombie eats it again, until it has been dead for long enough for the zombie to lose interest. As if this wasn't gross enough, he also suggests that well fed zombies might eat so much flesh that it fills up the entire digestive tract and starts to force older meals out the "back door", so to speak. In most cases, however, the flesh a zombie consumes will simply sit in his stomach and slowly decompose.
The fact that zombies' hunger is never satiated creates a new problem: Since the zombie will never be satisfied with what it has eaten, it is inclined to keep eating until there is nothing left to eat. This doesn't help the virus' cause in any way - keep in mind that the virus isn't trying to feed zombies, it is trying to create new zombies. If a new host organism is found, bitten, infected, and then devoured entirely, the virus has just lost a chance to infect a new host. How does the virus handle this problem? By setting different priorities for the zombie.
The virus makes sure that zombies are fickle - they won't eat anything that has been dead for more than a few minutes. This minimizes the possibility of zombies wasting their efforts on bites that won't result in new infections. After all, the virus doesn't benefit from zombies biting things that are already dead; it only benefits if the bite victim is alive at the time it is bitten, and survives the bite long enough to turn into a zombie.
In a similar vein, if the zombie(s) see a living person while eating a previous victim, they will often abandon the kill and pursue the new target. This isn't always the case, but as a general rule, the longer the current meal has been dead, the greater the possibility that the zombie(s) will abandon it when presented with a new target.
This is a delicate balance between the zombies' compulsions and the virus' objectives, and since neither the zombie nor the virus are sentient, there is a lot of back and forth between the two. Still, it works well enough to accomplish the virus' objectives in most cases. As long as enough bite victims survive long enough to turn into zombies, the virus will achieve its goals.
So What Happens To Zombies Who Don't Eat?
Basically, the same thing that happens to zombies who do eat. They wander around as best they can until they either rot away completely or get killed somehow. We tend to think that zombies only die as a result of intentional attacks by humans, and although this is certainly what we see in zombie media, it isn't the whole story. Zombies can fall to their deaths, or burn to death, or be crushed by falling objects or even by each other (imagine a horde of zombies besieging a fortified position in which humans are holding out - the zombies at the front of the horde will be crushed against the walls by the weight of the horde behind them).
And although zombies are very resilient and resistant to damage, there are limits to their durability. According to Brooks, environment has everything to do with how long a zombie will remain active and dangerous. In a desert, the arid conditions will slow the process of decay, prolonging the zombie's "life"; In this environment, a zombie could remain active for a century or more. A frozen zombie will become harmless for an indefinite period of time, but if and when it finally thaws out, it will be just as deadly as ever, and none the worse for wear; it doesn't matter if the zombie was frozen for a day, a month, a year, or a millennium. In a tropical rainforest, the heat, humidity, and abundance of microorganisms will speed up the process of decay, and the zombie will rot away in a matter of a few years at most. In most cases, and under most circumstances, the average "lifespan" of a zombie is around ten years, give or take, and allowing for significant differences in the physical condition of the zombie and the environmental conditions in which it exists.
You might have noticed that, in discussing the longevity of zombies, I didn't mention the issue of whether or not they had access to food. There is a good reason for this omission: In short, it is totally irrelevant. A zombie that manages to eat an entire person every day for as long as it is around will not survive any longer than a zombie that doesn't eat anything for the same period of time. Because the zombie's digestive tract has been a puddle of rotten slime since shortly after it became a zombie, eating provides absolutely no benefit to the zombie.
How Can Zombies Die?
The most obvious cause of zombie death is the destruction of the brain, but there are other options.
If a zombie is exposed to extreme heat for a sufficient period of time, it will either die or be rendered harmless. If the cause of the zombie condition is a virus or bacteria, intense heat will destroy the pathogen. Even if the cause of the zombie condition is something that is not susceptible to heat, if you set the zombie on fire, the muscle tissue and nervous system will be destroyed, and the zombie will cease to be dangerous.
As mentioned above, crushing a zombie is usually enough to render it harmless, whether the crushing is deliberate or accidental.
Also mentioned above, zombies do decompose on their own, but it takes a very long time for this alone to permanently disable them. The only clear explanation for this, as far as I am aware, was provided by Max Brooks (of course). Brooks says that the Solanum virus has unique properties that discourage decomposition: Every form of animal life, including microscopic organisms, are instinctively repelled by the presence of Solanum. The same idea applies to most fungi as well. Therefore, whereas a normal human body will begin to decompose immediately after death, due to the runaway growth of bacteria, fungi, etc, associated with decomposition, the zombie is virtually immune to these organisms. By the same token, insects and other creepy crawlies don't try to eat tissue infected with Solanum. Animals will flee from the scent of it rather than trying to scavenge a meal. In short, the things that make human bodies rot so quickly don't like zombies, so zombies rot much more slowly. Still, zombies do rot, however slowly. So, as I said earlier, depending on the environment and other variables, the average zombie will be rendered harmless by natural effects after about 10 years, but the actual number can be significantly higher or slightly lower, again depending on the circumstances.