401(k) withdrawals - early or otherwise - are not subject to FICA or Medicare taxes. That's because they already were taxed when they were contributed. (And of course, the earnings from the 401(k) contributions are not earned income and thus are not subject to payroll taxes for that reason.)
While 401(k) contributions are exempt from federal (and generally state) income taxes, they aren't exempt from payroll taxes - and as such, you'll see two separate amounts on your W2 and paystub if you contributed: the amount that is subject to those taxes, and the amount that is subject to income tax.
So, no, you don't have to pay payroll (FICA, Social Security) taxes on your early withdrawal. As for the penalty, that is basically an extra tax - so if you withdraw $1000, you pay income tax at your marginal rate plus 10% penalty; if your marginal rate is 25% [and you're not moving across a rate step boundary], you will pay 25%*(1000) + 10%*(1000)
.