Like Criptfeind said, currency is such a natural thing that I believe it would exist in any video game with an advanced trade system. Disallowing that really narrows things, but I'll try to speculate.
All in-game items could be put on a list. Steel armor would be above iron armor - it's more useful. A meal would be above a piece of bread. But would iron armor be above a meal? Would iron gauntlets be above iron boots, if neither is assigned a numerical value? If values are not assigned, then separate lists must be kept for things that have definite superiority in order. Such a system would require more - or different - player interaction. An individual in the game "knows" what they have, but not what the player wants/needs, as well as their own wants/needs. The most likely thing would be for the individual to define their needs and ask the player what they want in reward, unless a particular reward seems more fitting. This is basically questing as it is currently, but with an increased chance that the player already has the goal in their inventory.
To get armor, the player would have to complete "quests" from assorted individuals around town that have bits of the desired set, complete one big job or trade with someone who has a full set, or do a lot of work for the local smith while still managing to stay fed.
As for food, most people before currency worked all day for a full day of food. That's boring in an RPG. The player's best approach would be to trade loot from monster killing, raids, etc. Finding the right person to sell to would be a bit of a pain - jewelers didn't have much work in such a society, it just doesn't work. Some might only give you a couple of small meals for a gem, because they're short on food and don't have any use for it but further trade; nobles have more to offer, but do they really want to bother adding such a small thing to their collection? Lack of value presents a serious problem here. What's to differentiate that 4cm emerald from the golden spoon? The only solution I have to this is to undifferentiate loot, so to speak. Make all objects the same value and/or define it as units. Again, here value of loot isn't really based on value but the desire of in-game individuals and their current assets. Such a system would then be much more complicated to put in a game than currency-based systems, though entirely possible.
This was kind of rambly, but I think I got my points across. Basically, it's unlikely that this would be in place, but if so it would be a sloppy mess tracking the desires and stocks of every local.