Marmite is made from leftover brewers yeast, it is popular in South Africa, Australia, etc.
Marmite is made from yeast extract, a by-product of beer brewing. (Wikipedia)
So would it be considered halal, or is it haram?
Marmite is haram. Eat vegemite instead!
Kiwi-bashing aside, from their FAQ:
Is Marmite certified Halal?
Yes – The Halal Certification Authority of Australia has certified Marmite as a Halal product.
Is Marmite kosher certified?
Yes – Marmite is Kosher certified.
Is Marmite suitable for vegans and vegetarians?
Yes – Marmite is vegan and vegetarian friendly.
This same problem arose in Haraam or Halal? - Coke and Pepsi contain 0.001% Alcohol, where it was noted that e.g. Coke contains minute amounts of alcohol. So I reiterate the main ideas of my answer in this context:
If a substance is incapable of intoxicating even in large quantities, then it is not haram (insofar as to being an intoxicant; it could still be haram for other reasons).
Some people think that the words of the Prophet (peace and blessings of Allaah be upon him), “Whatever intoxicates in large quantities, a little of it is haraam”, mean that if a small percentage of an intoxicant is mixed with a large amount of a substance that is not intoxicating, then it is haraam. This is a misunderstanding of the hadeeth. ... if something is mixed with alcohol but the alcohol is a small amount and does not have any effect, then it is halaal and does not come under the ruling of this hadeeth. -- Islam Q&A, in the context of non-alcoholic beers
The prohibition applies to the substance as a whole, not to it's individualized parts:
Sheikh Salman al-Oadah astutely observed: "The percentage of alcohol mentioned has no effect on the ruling. The ruling applies to the drink itself taken as a whole and not to its composition." -- IslamToday.net, also in the context of non-alcoholic beers
It's reasonable to believe that even a large amount of Marmite is incapable of intoxicating, and thus prohibition due to being an intoxicant does not apply.