What does it mean that the security of 256-bit ECDSA, and therefore Bitcoin keys, is 128 bits? I mean, if I have approximately 2^256 possible points on the elliptic curve (thus possible public keys), and therefore private keys, doesn't that require approximately 2^256 computations to find the public key (or slightly less if the key is reached early)? From this it looks to me like the security is around 256 bits?
You would be right if exhaustive search was the only way to determine the private key for a given public key. That is not the case however. There exist algorithms that can do this with approximately √n operations (if the number of points on the curve is n). They are practical too (apart from needing an infeasible amount of computation): for example, they don't need much memory. Specifically, variants of Pollard's rho or kangaroo algorithm can be used to solve discrete logarithms on elliptic curves.
If security is 128 bits, then why do we even have a 512 bit seed? I mean, why isn't it 128 bits, because the extra bits don't increase security?
Conservative security. Having a seed that is less than 128 bits of entropy would certainly be detrimental to security, and more than 256 bits is unlikely to be helpful. BIP32, the standard now almost universally used for key derivation, uses a 256-bit key + a 256-bit additional "chain code", for master keys. In retrospect that may have been overkill (disclaimer: I'm the author of BIP32, and I certainly didn't know as much about cryptography back then as now), but it's also relatively cheap, in that the master keys are rarely observed by humans. While it's true that the security of individual keys is never more than 2128, it's not exactly true for seeds. Having seeds with more entropy does mean that one cannot just compute all keys from a wallet even with a machine present that can perform 2128 computations. This is the intuition that underlies making master keys and seeds larger, but again, this is overkill.