What is the safest method managing a large number of receiving Bitcoin addresses? Say I want to run a big project, where users can continually request new addresses to deposit Bitcoins in their online account. I suppose I will have to pre-generate thousands of Bitcoin key-pairs and import them into a running instance of bitcoind on my server. Each time a user requests a new address to deposit Bitcoins into his account, I will assign him a new address. Then bitcoind will notify me when any of the imported addresses receive a transaction.

First question: Is bitcoind capable of monitoring thousands of addresses in real-time? Should I plan a dedicated machine for this?

Second question: Since I will need to move received Bitcoins to a cold storage and also make payouts automatically many times a day, I will need to store the private keys on the online server as well. I can have wallet.dat password-protected but what is the safest method to automatically unlock the wallet, move funds and then lock it again without the password being possibly compromised? I don’t consider it safe if the password appears anywhere in code, config or database. And I don’t want to enter the password manually several times a day.

Third question: Will bitcoind generate a new “change address” every time I move funds from the receiving address to payouts and cold storage? I ask because if bitcoind used one of the imported addresses for change, it would appear as if client received Bitcoins.
You don't want to be storing any funded keys server side, there's an almost constant steam of hosts being compromised to steal funds. Most Bitcoin systems use something called a "hot wallet", and move the rest onto individual paper wallets outside of the servers control. It's then the administrators role to move funds back and forth to keep the hot wallet funded. This significantly reduces risk, and means that an attacker can gain at most the amount of funds in the hot wallet. 


  Is bitcoind capable of monitoring thousands of addresses in real-time?


Yes, but you really don't want to be storing anything more than a small hot wallet on a server. If your security isn't perfect then it's just going to be stolen. If it was used to 


  what is the safest method to automatically unlock the wallet, move funds and then lock it again without the password being possibly compromised?


You can't be sure. Even if the wallet is "encrypted", an attacker can just sit on the server and wait for you to unlock. Again this is why you need to be using offline storage and hot wallets to mitigate the damage of the server being compromised. 


  Will bitcoind generate a new “change address” every time I move funds from the receiving address to payouts and cold storage?


Yes. This is why all addresses presented to the client are single-use. You make a new receiving address each time for the hot wallet bitcoind, and never show it to the client again. They don't need to, their funds aren't restricted to any particular Bitcoin outputs. Their balance is just an external value in your database that you happen to hold the funds for. 

Ideally the setup looks like this: 

Server:


A bitcoind hot wallet, makes new receiving addresses and presents them to a client. Using walletnotify or blocknotify it updates the received balances for each user to an external database like Postgres or Redis. 
A check script makes sure the bitcoind never stores more than 50 BTC in it's wallet, if the balance goes above 50BTC a script runs that generates a new key with a deterministic public key (the server never has to know the private key to do this) or uses a pre-generated list. It sends the excess off to this address to keep it safe.
If the wallet doesn't have the funds to pay a user when they make a withdrawal request, show a soft effort and notify the administrator that the hot wallet needs to be refilled. Explain this is for the protection of the user. 


Offline:


An Armory wallet that holds the private keys of the cold wallet. Ideally this would be completely offline, with a paper backup in a safety deposit box. 
The control is only to the administrator, who knows the address of the hot-wallet refill on the server. When needed they move funds back up to the server as per notifications


Very involved, but it's roughly how other systems work, and it's got to be that way unless you want to end up like http://inputs.io/ who lost an entire 4000 BTC hot wallet due to negligence. You can never be too paranoid in situations like this. Your maximum loss in this case would be the 50BTC hot wallet, which is better than losing everything. 

Play safe.