Why do we need a mining speed above 4.3Ghash/s? I believe there will be a simple flaw in my understanding somewhere.

From what I can tell for any given block you increment a nonce up to 2^32 (4294967296) per second (and the timestamp every second) in order to find a suitable hash.

Thus if you have a mining rig that can do 4.3Ghash/s, you can cover all possible block hashes in any given second.

What am I missing here, and if this is the case, why do mining rigs with this specification or higher not find all the new blocks?
You assume that there exists (exactly?) one block for each work unit. This is not true, there are many variables (timestamp, nonce, transactions in a block, extranonce inside the block's coinbase transaction, ...), and all of them influence the block's hash. Each hash has a chance (as of October 2013) of less than 1 in a billion billion (1.15*10^18 to be precise) to be below the difficulty target.

Each miner searches a different part of the search space (which is, for all intents and purposes, infinitely large), hoping to find a valid block before anyone else does, but there is no "progress" to be made: every attempt has exactly the same chance as any other attempt. The nonce in the block header is just a way of making a particular group of attemps faster to search through.