I have a Woocommerce website. I need to add a fee to an existing paid order. How can I add a fee and have the credit card charged even though the customer has already submitted the payment information (which we don't store)? Is it possibile? Do I need a plugin?
You can't charge an additional fee if you already captured the full amount the customer authorised.
The reason is because online payments when done through a payment gateway are nearly always a two-step process involving:
Authorisation: As the name indicates, this is where the customer authorises that a certain amount will be charged against their card by the merchant. Your payment processor will verify that the customer actually has the funds and block them so that the customer can't spend them (to the customer it'll look like it was already deducted).
Capture: This is where the funds actually "move" from the customer's account to the merchant's account (technically nothing moves, just credit and debit accounting entries are made at the banks involved).
http://www.paymentsgateway.com.au/what-you-need-to-know/payments-gateway-authorization-and-capture has a good explanation on this process.
Authorize.net uses the same model as you can see from their documentation: https://support.authorize.net/authkb/index?page=content&id=A510
What to do in your situation?
If this is an isolated incident where you were meant to charge the customer a fee but forgot to, then either have them pay through a different way or waive the fee.
If you need to charge a fee for every single customer then they must authorise the total amount, even if you capture for example 95% on order completion and 5% afterwards.
Whether you can do these partial captures depends on Authorize.net and how you set up WooCommerce.