In medieval Ireland, social hierarchy was arranged around the ownership and renting of cattle instead of land, unlike other places in Europe. By renting cattle from an aristocrat, you became his client and were required to furnish him with food taxes, provide him with labour and occasionally host the aristocrat and his band of household warriors. Depending on the value of cattle rented by an individual, they would have to provide dairy produce like cheese, milk and curds as a form of food-rent. These peasant clients were required to furnish a labour tax as well; depending on the needs of their patron, they might have constructed fortifications (for example, I believe the 12th century King of Connacht, Ruaidrí Ua Conchobair, levied his clients to build a defensive canal) or participate in a communal harvest. They may have been required to join their patron's military forces as well, but warfare in early Ireland is a very contentious and unclear subject - we don't know if armies were small, permanent bands of warrior-aristocrats, levies of farmer-soldiers or a combination of both.

Rent/taxation was different for commoners and the aristocracy. Irish law made a distinction between a 'base client' (a commoner) and a 'free client' (member of the aristocracy in clientship) who enjoyed more privileges. A lower aristocrat could become another's client by renting cattle from him, and had the ability to rent more cattle at a better deal. The food tax still applied to this free client, but he was also required to join his patron's household warrior band when at war. It's possible that free clients were permanent members of the household guard, and had subordinates to take care of the land and livestock that they rented from their patron.

By the 10th century, the position of provincial kings had become more centralized and powerful, and a geographical administrative unit called the tricha cét (compare with the Anglo-Saxon hundreds) came into being. This system seems to have originated as a way to simplify the process of mustering military forces, but also became an administrative unit used to asses taxes. In 1106, the bishop of Armagh received a tax of 'seven cows and seven sheep and half an ounce [of silver] from each tricha cét in Munster', indicating that these units became an easier way for rulers to raise collective taxes from large geographical areas.

In addition to the fantastic specific answer for Ireland given by depanneur, I think a more generalized answer is also useful.

For most ancient kingdoms, there were two primary forms of 'taxation'. One is food, the other is labour. These two generally go back as far as recorded history.The exact form they were exacted could vary. Some states had almost total control over agricultural production (common in Ancient Sumeria for example), and the state and church in those worked together to disperse said food. Tenants would farm the land with excess going to the state. In many cases, food/rations also formed the 'pay' of artisans and soldiers working for the state. Even in states where a currency was available, taxation could still be paid in food stuffs. As to how a particular state set it's 'rates', in general this would be determined by the needs of the state, weighed against the requirements of the tenants on the land for subsistence. That said, it would not be uncommon for food levies to be extreme. Grains were extremely valuable in the ancient world because they were relatively long-lasting. For example, the wealth of Ancient Mesopotamia was almost entirely based on agricultural production; there was little to no wood or metals, and thus it was the state surplus of grain that was used to trade for these necessities.

Speaking of artisans and soldiers, this is where the 'labour' often comes into play. Many states levied military service on citizens during the months where no planting/harvesting was taking place. That military service can be more generalized as state labour though, since often 'soldiers' would be put to use in other areas. The Roman Legions and their building of roads during the Republic (when they were still levied labour) is one such example. Perhaps the most famous example is the constructions of the Egyptian state. It is now thought that most of the large temples and funerary monuments of Ancient Egypt (including the Pyramids) were largely constructed from levied labour during the off-season. This also may have served a practical purpose of keeping the people busy during the periods of year where the land was not being farmed. A similar argument might be made to rationalize the near constant campaigning of the Roman Legions during the early Republic.

At any rate, when you don't have currency, the direct needs of the state (food and labour) are met with quite literal taxation of the two.

Speaking specifically about Ireland around 400AD here, other tribes may have been similar but I cannot speak to that as I'm simply a fan of history.

I know around that time that the high king, Ard Rí world demand tribute from the lesser kingdoms, and certainly more powerful tribes would have done so to their weaker neighbours, in the form of cattle, alcohol, or other valuable goods. Their was no standardised money outside of Dublin, Baile Atha Cliath, where the Vikings would eventually bring in coinage. Cows were considered a superior currency by many tribes as they could not be stolen as easily and served a purpose; you can't milk a coin or eat it as far as I know. As to the meat of your question, "taxes" were the fruits of a tribe's labour. The chieftain led the tribe and thus the cattle were his by proxy.

Say you are a chieftain in Munster, Mumaidh. The king, Rí of Munster or neighbouring tribes may demand tribute from you, say if you were involved in a petty squabble and lost, and you would use your tribe's wealth to pay such a tribute, say five cows.

I know this is very specific, but I hope it helps give you an idea of how taxes may have worked in certain ancient kingdoms without a standard currency. Again, I'm not a historian, rather a humble fan of it. If I've made any mistakes feel free to correct me.

Reading the laws of Hammurabi, from 1750 BCE give or take, and based on older laws, such as ur nammu there are references to amounts of metal translated as talents. This seems to be money. But I am nitpicking your "Before" question.

When money was hard to come by, taxes were extracted in labor. You would pay your taxes to your lord liege in the middle ages by fighting a war for him. If you were a peasant you might have the ability to build a road or fix a castle or house. Also you were expected to farm the lord's fields for X number of days a week depending on the custom. This only applies to western europe.