You can charge them a flat fee, say 0.0005BTC
But who's to say that will actually be enough to cover the miners fee? What about handling of this problem for alt-coin clients as well?
Is there no way to query what the client will generate as the miners fee in advance?
A flat rate, if high enough, should cover the fee on long term.
If you really want to tell the user the exact fee before transaction, you should do it this way:
1. User tells you the amount he wants to withdraw
2. You search your UTXO set, find suitable UTXOs, calculate the fee and you tell the user
3. You lock the chosen UTXOs for a few minutes (not to be used in other tx)
4. If the user accepts the fee, you will proceed