Is it PCI compliant to generate a token for every card used for processing, regardless of whether the client asked for his card to be saved or not?
Short answer: Yes, it is PCI compliant.
The PCI DSS requires that card data be "rendered unreadable anywhere it is stored"; encryption and tokenization are the two most common methods. But all that tokenization does is to provide a way to reference card data without some places storing card data. It is most often used to permit a merchant to store and manipulate tokens handed to them by their processor; the processor is still storing the card data (encrypted) but have generated that token to allow the merchant to "use" the card without "having" the card. It wouldn't make much sense for a single entity to generate tokens for their own use; tokens only work when they reference stored card data, and if you're storing card data, generating your own tokens for them won't alter your scope a whit.
The PCI DSS does not deal with the question of the client asking for the card to be stored or not. When a client uses a credit card, they are implicitly accepting that their card data will be stored by one or more intermediary parties during and after the credit card authorization and settlement process. While such requirements are not part of PCI DSS, credit card transaction records must be stored long enough to support card dispute and chargeback purposes. That includes card number - you need the card number to handle a chargeback request. The client's ability to say "Hey, I didn't buy that" and get their money back is one of the value-added services use of a credit card provides, and the card data need to be stored for that to happen.
You haven't specified which PCI-covered entity you're concerned about. Merchants can avoid having to store cards using tools like tokenization. Processors generally need to store cards. Other "Service Providers" may or may not need to store cards; depends on what service they're providing.
If you're concerned from the POV of a client - you really can't do much. You deal only with the merchant, who passes the card through a minimum of 1 and possibly more than 1 other entities during the act of processing. All of them are allowed to store the data as long as they protect it as dictated by the PCI DSS. The only way to opt out is to use cash.