First we need to discuss what wealth is. Is it just the amassment of valubles? In the 16th-18th century, rulers thought so. This notion is called mercantilism. This idea was rejected by Adam Smith in book IV of The Wealth of Nations.
The current meaning of wealth is not the amount you own, but rather how much you can consume (sustainably). Formally, the definition is Total of all assets of an economic unit that generate current income or have the potential to generate future income. This is of course the same amount as the amount that you can sustainably consume. This means that we can measure wealth either as production or as consumption.
Thus, there is not just how much riches you own, but also how much you can create. Also, remember that you cannot consume money. You can only consume goods and services. Amassing riches has little value in itself. It is mainly a way (for an individual or group) to postpone consumption to some point in the future.
Thus, wealth is measured not just by the current riches you own, but also by the ability to create more riches in the future. A man with 100,000 and no income is poorer than a man with no money but with an income of 50,000 a year.
These things [...] don't generate new wealth.
But they do.
Labor
Let's look at how labor increases wealth by looking at a couple of examples:
Example 1. I work at a farm. The result of my work is some farm produce worth X. For that I am paid Y. The farmer that hired me will receive X-Y.
The net wealth gain for the society is Y + (X-Y), or X.
Example 2. I work as a barber. I charge X for a haircut. The customer gets a haircut worth X. Net wealth gain for the society is X + (X-X), or X. Since the haircut is consumed immediately, the amassed riches don't increase. Note that the customer didn't lose out - to him a haircut was worth at least X or he wouldn't have gotten one. In macroeconomic terms the GDP increases by X and net savings is unaffected.
Trade
Trade increases wealth by transferring a good or a service to someone that values it higher.
Example 1: I buy a used car from a neighbour for X amount of money. I get a car that is worth Y to me (Y>=X, or I wouldn't have bought it). My neighbour gets X for a car that was worth Z to him (Z<=X, or he would have kept the car). The wealth produced is (Y-X) + (X-Z), or Y-Z, which is >= 0 because Z<=X<=Y. In GDP terms the wealth produced is X - X, or 0, because GDP only measures how much is paid.
Example 2: An electronics company imports batteries from China for 10 cents each. They sell the batteries to customers for \$3 each. The wealth increase in GDP terms is \$2:90 per battery. The wealth produced is shared by the electronics company, the shipping company, the store salesman and any others that provide services to the electronics company.
Innovation
Innovation is both the invention of new and the improvement of the existing. Actually, most innovation is small improvements in existing technology or design.
Example: I improve a machine that makes nails so that it can make twice the number of nails in the same time. This means that more nails can be produced (and thus consumed) using less labor.