While I can't comment on their hiring practices for people without a college degree (even though I know a few people who have had successful careers with the govt without any college experience), I think a more likely reason heavily tattooed people could have a problem working at the government is that they are more likely to be people who are difficult to clear (heavy drug use in the past, surrounded by people who are heavy drug users, etc.). They clearance process is honestly really stupid. Having tattoos will not disqualify you, but surrounding yourself in people with bad habits will.
As someone watching close friends get hired weekly to places where they "can't say where they will be working", it seems like Uncle Sam will hire anyone with a pulse who even expresses an interest in security.
And if not, the people will just go make twice the money at a defense contractor....
edit: I think a lot of the "red tape" belief for the government comes from people who are on the outside of this industry looking in not understanding the hiring process. It is the opposite from a place like Google.
Basically. You end up in someone's office and they talk to you for a few minutes and know if they are going to hire you within the first 3 minutes of the interview. The important part though, is that you are clearable. Since this is a long and expensive process, a lot of contractors put on their job requisitions "must be able to obtain a security clearance". They will believe you if you tell them you are clearable. That's because getting denied a clearance can be a big deal if you want to work at the gov't later. It also is a auto-fire for the particular job (I would know. The clearance I was denied was the best thing that ever happened to me)....