Each user gets his own bitcoin address where the user can make deposits.
This is a bad idea. You should use a new bitcoin address for every transaction.
How should I handle this?
You should have a database of bitcoin addresses. Anytime someone needs to send bitcoins to you, you should choose an address that you haven't previously chosen from this database. You should identify in the database which chosen addresses are for which transactions. That way once the address receives the payment, you can look up exactly what that payment was for.
I'm running a debian root with bitcoind - should I generate for each user a own account and assign addresses to this accounts or should I create only unassigned addresses and send the bitcoin to the "main" storage address and only update the amount in the mysql database?
I'm having a difficult time determining what you are asking here.
And another question regarding security: I only want to store 5-10% of the bitcoin in a "hot" wallet and refill this amount if necassary to provide security.
If you are only receiving bitcoins (and not sending them), what is the purpose of a "hot" wallet?
What is the best method to store the other 90-95%? Paper wallets?
Armory offline is a good solution for cold storage, paper wallets are ok too as long as you are careful and understand how to use them safely.
And how can I automatically refill the hot wallet?
No.
No, no, no.
If bitcoins can be removed from cold storage "automatically", then you are lying to yourself (and your users) and you don't have any cold storage.