(Insert usual disclaimer that I'm just a random guy on the Internet, not any kind of certified tax professional.)
But once I withdraw the money, how is that money taxable?
If I'm understanding your situation correctly, you want to look at the instructions for form 8889, under Excess Employer Contributions. It simply says, "If the excess was not included in income on Form W-2, you must report it as 'Other income' on your tax return." There doesn't look to be any particular wording beyond that, so I'd just put it on Form 1040 Line 21 Other Income, and label the line really specifically like "Excess Employer Contributions distributed from HSA".
Also there is no mention of whether any FICA taxes (social security and Medicare) apply to these amounts.
You say that this was entirely contributed by the employer. But even for cases where one contributes directly through payroll with an optional pre-tax deduction, this is usually implemented as a "salary reduction agreement" where the company is actually paying less money in salary (and thus less showing up on the W-2) and just contributing to the HSA account instead. It's listed on the 8889 as an "Employer Contribution", even if in fact one sees it as a deduction on one's pay stub.
In either case, since the company didn't pay you the money as salary (and merely contributed to the HSA instead), I wouldn't expect any FICA taxes to be owed on it. The fact that the IRS wants it listed under "Other income" instead of "Wages" also implies to me that it doesn't count as salary that needs FICA taxes.
Presumably, if people abused this in some way (like getting their employer to deliberately over-contribute each year and getting a refund in some sort of crazy scheme to try to reduce their SS taxes) the government would get rather upset and probably call it some sort of tax evasion. But for the amounts involved here, particularly as you're following the instructions listed, I just wouldn't worry about it.
Assuming that I withdraw excess contribution and report everything on Form 8889 and Form 1040, is there any further action required from my previous employer?
It's your HSA, so I wouldn't think so. Since the eligibility for HSAs is based on what you do, and not what they do (you could, for instance, get covered by a different HDHP and they wouldn't be notified nor really care), I don't think they have anything more to do with it.
Also I am not sure how to calculate amount of interest attributable to excess contribution. I have only around $0.20 of total interest this year.
The bank holding the HSA could probably help with that, as I'd expect it to be a normal part of the excess contribution withdrawal process. If not, I'd just make a reasonable effort based on the interest rate, amount involved, and number of days that the excess was in the account.
Also keep in mind that in general when filing taxes, anything under $0.49 can round to $0. At some point, one can only be "as honest as the law allows".