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
I think the former seems like the way to go - aim for something which covers fees on average.