What is needed for a city to be called a city and not a town or a village? Are there minimum regulations regarding population or land mass that distinguish a city from a town, township, village, etc?

Where? It could differ from country to country. In the UK normally, but not exclusively, a city will have a cathedral. I can remember when Southampton was changed to being a city instead of a town, Southampton doesn't have a cathedral.

Newport had a cathedral for years before it was declared a city in 2002. I think there are some anomalies in our system.

The webpage below gives details of what city status means in the UK today. Nowadays, a town becomes a city by virtue of letters patent issued by the sovereign. This usually happens after a competition, often organized to mark some “milestone” like the end of the second millennium or a royal jubilee or anniversary.

A number of towns are called cities by “prescriptive usage”, i.e. they’ve been known as cities for centuries, and so the title is recognized even if there’s no charter or letters patent.

When the Christian church established itself in Britain, it naturally set up its bishops’ sees in what were then the main towns. Many of these towns are no longer as important as they were, but because of their former pre-eminence they became cities (possibly by prescriptive usage). So there’s a widespread belief that a cathedral makes a city, but (as you can see from the webpage) this isn’t strictly true.

http://www.dca.gov.uk/constitution/city/citygj.htm

Cities in both U.K. and U.S. have to be incorporated, and approved by the State, or the Crown

In the U.S., "city" and "town" can be used interchangeably, depending on simple local custom. The suburb (of a good-sized city) in which my mother lives is incorporated as a city itself and is always referred to as one, though its population is about 9,000. Her hometown, with a population of 12,000, is also incorporated but is described by most of its residents as a town.

An unscientific poll of persons visiting my household this morning turned up the prevailing view that a "real" U.S. city has to have a population of 50,000 or more. Anything smaller calling itself a city is suffering from delusions of grandeur.

In summary, there is no international standard definition of city, even in the English speaking world so when reference works specifically call a place a city or town there will often be a degree of arbitrariness about it.
In the UK, a city is strictly defined as a town which has been known as a city since time immemorial or which has since been granted the right to call itself a city by a charter. The presence of a cathedral may affect the decision to confer this status but is not a necessity.
In the US, many small places have optimistically had city put in the name in the hope that they would grow into such. Interestingly, parts of cities in the US are now calling themselves "Village" to make themselves seem more amenable.
https://en.wikipedia.org/wiki/City

Leeds doesn't have a cathedral, and we're the third biggest metropolitan area in the country, so it's not all about churches anymore...

For the record (once again):

UK cities without cathedrals include:
Bath, Cambridge, Hull, Lancaster, Newport, Nottingham, Plymouth, Salford, Southampton, Stoke-on-Trent and Wolverhampton.

UK towns (and one village) with cathedrals that aren't cities include:
Bury St Edmunds, Chelmsford, Blackburn, Guildford and Southwell.

Clearly, I mean Anglican cathedral, as several towns without city status (like Shrewsbury near me) have Catholic cathedrals.

In Israel, most cities are defined as such once they get a population of 20,000. This is unless the settlement in question is already defined as a kibbutz or a moshav, which have definitions of their own. I would venture a guess and say that a very small percentage of cities worldwide have cathedrals.

This website provides those Key Facts about UK Towns and Cities which help to instill civic pride amongst their citizens. These include details of towns with the civic honours of city status and/or a lord mayoralty or those which have a university or a cathedral. Other factors which boost civic pride include having a good football team or winning the national Britain in Bloom competition, and this website will show which towns and cities have been the most successful.

http://www.lovemytown.co.uk

Largest Towns without City Status (town, population):

1 Reading 218705 2 Northampton 215173 3 Luton 211228 4 Bolton 194189 5 Bournemouth 187503 6 Swindon 182441 7 Southend 175547 8 Middlesbrough 174700 9 Milton Keynes 171750 10 Warrington 165456 11 Huddersfield 162949 12 Slough 155298 13 Poole 154718 14 Blackpool 147663 15 Ipswich 144957 16 Birkenhead 142968 17 Telford 142723 18 Sale 134022 19 Watford 131982 20 Solihull 123187

21 High Wycombe 120256 22 Gateshead 120046 23 Colchester 119441 24 Blackburn 117963 25 Cheltenham 116447 26 Doncaster 109805 27 Rotherham 109691 28 Eastbourne 109185 29 Worthing 109120 30 Sutton Coldfield 109015 31 Rochdale 107926 32 Maidstone 107627 33 Basingstoke 107355 34 Basildon 107123 35 Crawley 106943 36 Stockport 105878 37 Woking 105367 38 Gillingham 104157 39 Wigan 103608 40 St. Helens 102885

http://www.lovemytown.co.uk/CityStatus/CityStatusTable2.asp

List of UK towns with city status: http://www.lovemytown.co.uk/CityStatus/CityStatusTable1.asp

It varies from country to country. In Israel, a city retains its status as such usually once it reaches the population of 20,000. But there are places with more people which are not cities. And there are cities with fewer people. I don't know what the rule is, or even if there is one in all places.

The definition of a city will vary from state to state in the US. The Town of Sharpsburg, Maryland has a population of about 700, but it has a Mayor and Town Council and is a separate (and additional) taxing district from Washington County. There are many such towns in the county. The largest, Hagerstown, has a population of about 37,000 and is called the City of Hagerstown, and is also the county seat.

In the UK at least, I believe in order to be a city a settlement must have either a Cathedral or a University.

Actually, no. In the UK, city status is an award by the Sovereign, and currently decided by competition. Last one was in 2000 (results announced in 2002) when Preston, Newport, Stirling, Lisburn and Newry received it.
http://www.dca.gov.uk/constitution/city/cityhome.htm
and also follow the Results link there. it is purely a status thing and makes no real difference to anyone in practical terms.

In everyday usage there's a tendency to refer to a larger town (say a place with a population of over 100,000) as a 'city' regardless of its strict, legal status.

It really depends on where you are in the world: "Distinction between cities and towns

There are probably as many different ways of conceiving what a city is as there are cities. A simple definition therefore has its attractions. The simplest is that a city is a human settlement where strangers are likely to meet.

Richard Sennett, The Fall of Public Man, 1977, p. 39.[34]

The difference between towns and cities is differently understood in different parts of the world. Indeed, some languages other than English use a single word for both concepts. Iberian languages typically use a three-way designation (Catalan: "poble", "vila", "ciutat"; Galician: "aldea", "vila", "cidade"; Portuguese: "aldeia", "vila", "cidade"; Spanish: "pueblo", "villa", "ciudad"-respectively "village", "town", "city"); Italian: "villaggio", "paese" "città"-respectively "village", "village/town", "city/town"; but other Romance languages don't (French: "village", "ville").[citation needed]

Even within the English-speaking world there is no one standard definition of a city: the term may be used either for a town possessing city status; for an urban locality exceeding an arbitrary population size; for a town dominating other towns with particular regional economic or administrative significance. In England, city is reserved for very large settlements and smaller historic settlements with a Cathedral (e.g. Lichfield), while smaller settlements without a Cathedral are called towns, and smaller still are villages and hamlets.[citation needed] In the US city is used for much smaller settlements."
-from https://en.wikipedia.org/wiki/City_status

https://en.wikipedia.org/wiki/Royal_charter

In UK towns can be granted City status by Royal Charter, without the requisite Cathedral.
A good example of this is the University City of Cambridge.