I employ quite a few people with facial tattoos, but that's in the tattoo and piercing industry.

I think that your options are going to be based on the area that you're in. If you're in a larger city, specifically one with a "trendy" area, your chances of finding a job outside of the industry are going to be better. On the flip side, if it's a smaller town, well...

Warehouse, mill and factory employers don't seem to mind too much. Temp agencies may be a good place to look as well.

If you're only looking into the Army as a last chance and you don't really want to be there, personally I would suggest that you exhaust any and all options before signing up.