Many students write their math homework assignments in a messy, barely readable way. When I was a student TA/grader, I didn't have the right to ask them to rewrite them. But as a math instructor, I wonder if it is appropriate for me to ask those who write their homework poorly to rewrite it, otherwise it won't be graded (even writing it in the syllabus)? I am also planning to show them some examples of nicely written homework. As a more exaggerated question, are professors in United States even allowed to do so?
In most other fields, university and college instructors often require that students type their work, and submit a typed, spellchecked, referenced, and otherwise professionally written document. Students are expected to be able to use technology in order to produce work. This is a norm, and instructors will return work to students if it does not meet this expectation. This is entirely permissible (this kind of policy generally falls under the umbrella of "academic freedom").
In mathematics, we typically cannot require that students type their work (at least, not in lower-division classes which are attended primarily by non-majors)—the equation editors in packages like MS Word or Google Docs are somewhat arcane (and produce poorly typeset mathematics, anyway), and TeX/LaTeX are more difficult to learn and are not taught at an earlier level (hence we can't rely on students knowing how to use these tools). This means that we usually have to accept hand-written work in mathematics.
That does not mean, however, that we must accept work that is not professional. Aside from the pragmatic aspects of grading work which is sloppy (which are probably the most important reasons to return illegible work), the work that a student produces reflects upon them. When they choose to present illegible, sloppy work, they are presenting themselves unprofessionally. Part of the college experience is learning to present oneself well to others.
The only caveat I would make is that there are certain disabilities (e.g. dyspraxia) which can make it difficult for a student to turn in neat handwritten work. However, in the US, accommodations for such disabilities usually need to come from your "Office of Accessibility and Inclusion" (or the local equivalent thereof).
 And, to be fair, I would expect the same to be true in other notation heavy fields, such as physics or chemistry.
I require typed homework in my classes. This requirement is traceable back to a program level learning outcome that says that students will be able to communicate mathematics in a professional fashion.
I’ve had students question this requirement, but they can’t reasonably claim that they’ll be able to produce hand written reports in a professional setting.
At a technical level, I tell students that MS Word and Google Docs (they have Google Apps accounts as their campus email) both have reasonably usable equation editors. I encourage grad school bound students to learn LaTeX.
What you are "allowed" to do is somewhat of a local question, but there aren't a lot of restraints on tenured faculty. Student feedback can be taken into account in tenure decisions, however.
But, if you are clear that homework must be readable to be gradable then something like the following might be workable. I employed it for this and other reasons. I'll tailor the description a bit to your case but it is an example of generalized regrading. My field was CS.
When a student turns in work, it is graded and commented. The comments are important. If it is unreadable, it might get a grade of zero.
For any reason, if the student is unsatisfied with their grade, they may redo it and resubmit it for regrading. However, the old work must be submitted along with the new, in a folder naming the student. The regrading won't allow "full marks" on the new work, but (my standard) 90% of the gap between the initial grade and full marks. So, if the original grade was 60% (lost 40) they can earn back all but 4 points.
I realize that this doesn't scale, but it was possible for me to grade around 30 students very efficiently, since I had the original grade and comments. I also required that students highlight the changes from the original so that I didn't need a full analysis of the new work.
One caveat, however, is that you might need to limit the number of regrades. I only needed to do so when an individual was in danger of getting behind because they weren't spending sufficient time on new work, but there was no fixed limit. Usually only zero-two retries were needed for students to get a grade they were satisfied with and I was satisfied with their learning.
Using techniques like this, I was seen by the students as "tough but fair". I didn't find it burdensome at the scale I had.
Another caveat is that you need to convince students not to be sloppy with their first attempt. This occasionally required a bit of counseling.
An advantage of this scheme was that I never got complaints about my grading. They just brought the work up to my standards.
For more on my grading scheme see this answer to an older question.
If homework is actually unreadable then it is appropriate to give a zero grade for that particular question and continue to grade the rest of the paper.
If it doesn't meet your arbitrary standard of neatness but can be understood then it is completely inappropriate to ask and likely to be discriminatory. You will be penalising students who are legitimately trying their best. You will be choosing to satisfy your personal biases over assessing and improving their mathematical skills. And your students will have every legitimate grounds to detest you.
As a personal anecdote, about a teacher who came close to stopping me perusing mathematics any further, when I was studying A-levels (16-18) he gave back the first bit of homework he said "you and I are not going to get on". I had got every question right, and the only comments he'd put on the work were about messy presentation.
Week after week I'd hand in work with every question or almost every question correct, trying my level best to present as well as I could, and the only comments I ever got back were on the presentation. Eventually I just gave up trying and handed in my work sloppily and quickly done. Fortunately at that point he realised I had been trying and never commented on my presentation again. Eventually we got on well, and I went on to study Maths at university. I wonder sometimes whether he learned anything from the experience. P
Now, I have dyslexia and (then undiagnosed) ADHD and I'm sure some would like to dismiss any consequences of their policies as the responsibility of disability rules but there are a great many people who never get diagnosed - particularly people who are otherwise bright and capable. Your policy will hurt people who are good at maths and trying their best.
In my (physics) classes, the students are advised (in writing) that submitting poorly written or presented material may result in inaccurate evaluation of said material.
Note that contrary to others, I require my students to submit assignment in person and handwritten on paper: this reduces the risk of copy-pasting from the web or hiring a third party to complete the assignment on behalf of a student.
As a TA (material science), I always told the students that if I could not read the critical steps but the results were somewhat right, I would take up to 10% off - because becoming an engineer includes (or it should include) learning how to neatly share your ideas. If the entire homework was complete but unreadable (happened only 2 times in 3 years), I took 60% off. Enough to scare them, but not enough to screw them.
Edit: obviously, that was discussed with the professor at the beginning of the term, and the students were warned about it.
Try to give students the benefit of the doubt and act not as if they know what to do and refuse to do it, and instead that they don't know what to do.
My impression is that US high school math students are trained on strategies for multiple choice questions, and what's necessary to write in free response exam questions that will earn them full marks. (Once I asked a student why they consistently wrote → instead of = on a paper. They said they were taught that misusing an equals sign could lead to losing points, but there were no such rules about →. So their teacher told them to just use →.) I don't get the impression that they've been graded on the quality of their written homework, and that college is the first time they are asked to do such things.
So I tell them near the beginning of the course that clear presentation of written work is one of the learning objectives of the course. I try to give them examples of good and bad student work. I use a rubric that accounts for organization, legibility, complete sentences, etc., and make sure they see the rubric before they turn in their first problem set. And when a handful of students are inevitably surprised by their low scores, I point out all of these things that I have done and maintain that these are my expectations.
If you're in charge of the grading policies for your course, you could do some of these things, and also allow for the first few assignments to be rewritten.
My field isn't math, but I more or less required all of my students to type everything that isn't done in class in front of me, not only so that it would be legible, so that it could be submitted remotely if required.
In the real world, most documents in industry and academia are typed up, so it's good practice for them to submit assignments in type form. Consider it a good opportunity for them to practice formatting documents, as well as in using the software.
Outside of the practicalities, it's always appropriate for an educator to ensure that the material submitted to them can be correctly graded, it would be unfair to mark someone down who got the correct answer but was unable to articulate it due to messy script. The key is simply to be sensitive about it, and to ensure that they have access to the facilities to type up the document before making a big thing out of it.
Put your rules in writing, including rules about looking at the work of others and send a copy to your chair. If he's happy then you're allowed.
Even if you are required to accept handwritten work, it wouldn't hurt to tell them the advantages of using, e.g., LaTeX. That can save them time as well as reducing the burden on you.