This is actually not as complex as it sounds. The trick was that most tax collection was (until relatively very recently) very decentralised. As such, the assessors would most often be local people of the community (in England for medieval period and later this would be the Parish constable who was selected from amongst the wealthier and well-to-do members of the parish - not gentry or lords but local businessmen and householders). Now, remember that in the local communities of England very few people would actually be susceptible to paying tax - most people were tenants, so did not own property, and most of these would have incomes below the threshold for taxation which would usually be something like 'every X penny in the pound for those that earned over Y'. It was simply not worth taxing the majority of the population as they did not actually have enough to tax in any meaningful amount. That held true until well into the 20th century and even today something like 25% of all income tax revenue in the UK is paid by the top 1% of taxpayers and 90% of all income tax revenue is paid by the top 50% of taxpayers with the highest incomes. So 50% of all income taxpayers contribute only 10% of the total from income tax.

Property Taxes
The local constables would know precisely who owned property in the area as, you are correct, this formed the basis of the tax base for centuries - property usually was based on the monetary value of property per year rather than its potential sale value and again, assessments would be regular enough that the records would exist within the parish, the current constable on receiving notification from the county authorities of the new tax, would make the assessment based on those and go around the relevant tax-payers to inform them of the amount.

Income Tax

Income tax hit more people, as it was possible to be a tradesman or artisan who rented their place of business to avoid property taxes but be susceptible to income tax. This was one of the reasons it was so widely loathed as many who had not previously paid tax, now had to. However, it was still not applied to the population at large, it had to be on those whose income (whether from business, rents, trade etc) was over a certain threshold. What made this such a difficult tax to collect was that, unlike property valuation, it was far easier to contest how well you were doing. The lack of ready cash made the constable's jobs a little easier, as the complexity of debt and credit in a world with little ready currency meant that everyone kept records of who owed what amount and as such it was these records that tax estimates could be based. Tax-collection time normally fell around the quarterly markets when the amount of currency in the local economy would be at its highest for both assessment and taxation purposes.

Sales Tax/Tariffs/etc

These, as you are correct in assuming, were often beyond what local community officers could achieve, as transportation and distance often made this difficult. In fact, much of the early Exchequer organisation, apart from that part of 'central' government which ordered the localities to order the constables to collect the relevant tax, was concerned with the points at which goods (sales) could be taxed. These were usually in the forms of import or export tariffs. Initially these could be at gates of walled towns and on manufactured goods - the point at which the process could be easily located and identified. However, one of the largest surviving sources we have for internal and external trade to the England are the Exchequer Port Books. Every major port (and its associated minor ports) had to investigate every ship which docked in order to establish if it was engaged in local (internal) trade or was importing or exporting goods from overseas. These last would be what the tariffs were most often placed on as it was the most straightforward way of implementing a tax. Taxation of goods being moved around locally was often seen as near impossible to regulate as local smuggling, lying to authorities, and local vested interests could prove resistant to taxing goods at multiple stages of their journey whereas import/export from the country really only had one point of taxation - getting on or off the ship.

The important point to remember is that taxation required the cooperation of the authorities to do so, all of whom themselves would be subject to the same taxes. Tariffs were usually standing taxes that went straight to the Exchequer and seen as a royal right, whereas the taxation of your subjects was less regular as it was seen most often as an emergency measure. At least until the costs of war demanded it more regularly.

Kent, J., 'The English Village Constable, 1580-1642: The Nature and Dilemmas of the Office' Journal of British Studies, 1981 20/2, pp. 26-49

Saul, N. 'Taxation', in A Companion to Medieval England 1066–1485 (Tempus, 2000), pp. 281–283

Wheeler, J.S., The Making of a World Power: War and Revolution in Seventeenth-century England (History Press, 1999)