As a plumber, I run into this several times a week. If it is rusted like yours is, I don't even attempt to get the nut off from beneath. I use a Sawzall or hacksaw to cut the faucet off from above. Put your blade right where the valve body and base meet, at the gap, and saw right through it. The bottom of the faucet will drop right out of the bottom. It is always easier if you can pull the hose out first, but if you can't, it just takes a little longer because the blade jams on the hose flopping around inside the body. Trust me, this is easy.
Bruce