Certainly, the primary problem is getting admitted in the first place. These pre-reqs are not usually checked by the computerized registration system once you are in graduate school, partly because it is assumed that, upon admission, you will have already met them.Also I read on some forums that a lot of times majority of these pre-reqs are waived after talking to the professors.
Have you checked out UT Dallas? Technically, UT Dallas has zero computer science prereqs prior to admission:
UT Dallas also ranks better than UT Arlington. The only CS departments in Texas that are better than UT Dallas are Austin and TAMU.
But I don't know what UT Dallas actually does in practice once they admit someone without a CS background. So you may want to ask them to at least see if they give you some hints about what is actually done. I would think they would have a policy in place since they have so many students. Or you could start e-mailing their hundreds of MSCS students one-at-a-time
Also, I don't know what the odds of admission are at UT Dallas without a CS background. As you probably know, UT Dallas is considered a safety school with a large number of international students. But the Admit Profiles at Edulix show that they do surprise people sometimes with a reject, partly because UT Dallas is more strict than other places about meeting the minimum GRE requirements.