So we are totally relying on bitcoin wallets to spend bitcoins?
While it is technically possible to create and sign a bitcoin transaction without any software at all (just pen and paper), it would be a difficult and extremely time-consuming thing to do. So, yes, we are generally totally relying on wallet software to create transactions for us.
And each time we make a payment, we need to back up a new private key and the old private key will become useless?
In this case, for each transaction we have to perform a backup?
That depends on the wallet that you are using. Most well written modern wallets use a system called "Hierarchical Deterministic" (or HD). This allows the wallet to generate a random seed value when it is first installed, and then to use that seed to generate all of its private keys in a deterministic way. You can just back up that seed once when you first start up the wallet, and if you every need recover, the wallet can rebuild ALL of the exact same private keys that it ever used from that same seed.
Some older wallets would pre-generate a batch of private keys that it was going to use in the future, and include those generated-but-unused private keys in the "wallet file" that users would back up. That way, the user wouldn't need to back up as often. As long as they hadn't used up all the pre-generated keys yet, recovery of an old backup could still recover all the keys that they recently used.
However, if the wallet you are using isn't a HD wallet, and it doesn't pre-generate keys for you then yes, you would need to back up each time you make a payment.
For people with paper wallets, if they decide to spend the coins, each time they make a transaction, they need to print out the new keys and store them?
Correct. This is why paper wallets are used as "cold storage" for long term storage of bitcoins that won't be used in the near future. It is a hassle to have to create a new paper wallet every time you create a transaction, but it is not a hassle to put the paper in a safe and leave it there untouched for a few years.
Occasionally someone doesn't understand this need to create a new paper wallet, and they permanently lose some of their bitcoins. I've had to explain this to more than one user after they made that mistake.
For multi-sign keys, each time we spend balance on that address, we also need to produce and distribute multiple private keys to different ppl?
With Multi-Sig, people should be generating their own keys. They shouldn't be trusting someone else to generate a key for them. That would destroy the security of the multi-sig (since the person that creates the keys could secretly keep a copy for themselves without anybody knowing).
Just like you CAN re-use a non-multiSig address in bitcoin if you want to (even though it is not recommended), each participant in a multi-sig transaction also CAN re-use their key if they want to (even though it is not recommended).
You could build the transacitons using keys from a HD wallet, in which case the user would only need to supply you the master public key, and you could generate the additional public keys as needed.