If I generate a private key on mainnet now, would I be able to use it
at the same address on Ethereum Classic? What about testnets?
Yes, this is exactly how it works - Ethereum, ETC, and all the test nets (Ropsten, Kovan, Rinkeby) generate the address from the private key in the same way. Also other Ethereum-based blockchains, such as Expanse or Ubiq.
You can confirm this on MEW by going to the View Wallet Info tab, and trying the same (arbitrary, e.g. 0x0101...0101) private key while attached to different networks: the address generated will be the same in each case.
In what cases would the keys not give the same address on different networks / chains?
The address generation method is specified in the Yellow Paper appendix F. If the chain doesn't conform to this then different addresses will be generated.
A follow up question would be: since deployed contract addresses are
derived from nonce and sender address, does it mean if I deploy n
contracts on different networks and chains, the n contracts would have
the same set of addresses on different networks?
Again, yes.