You need to do two things to free up the licence.
1) Get the user to deactivate his licence in Tableau Desktop see here Move or Deactivate Tableau Desktop. This will send the information to Tableau to adjust the licvence availability. For completeness I would then get the user to uninstall Tableau Desktop too.
2) Delete the info you have against that licence key in the Customer Portal.
From experience, 1) is key in ensuring Tableau's data stays in sync with yours. I've had numerous occasions with users who no longer need the licence and I've then redistributed into the business. Sometimes by the time I find out they no longer need it, they've no longer got the machine they had it installed on, or the machine has been restreamsed so they're unable to perform the deactivation step. On rare occasions when the key has then been reallocated to someone else, that new user has had issues registering the key as Tableau believe its already in use. Tableau Support have to get involved to fix their data, and I've always been told to ensure the deactivation step takes place.
Jonathan - I can't comment on how Tableau Online works. I would imagine this is something your Tableau account manager can advise on, and suspect it's something Tableau themselves will need to resolve for you. I am going to attempt to branch your question to a new thread, as this is techinically a slightly different question from Sid's and it will have a different answer (a thread can only have 1 correct answer).