After starting a PhD in Mathematics, I realized I am more interested in Statistics - can I transfer to a Statistics PhD? I'm a first-year mathematics PhD student at an American university. 

When I applied to graduate school I thought I would be doing math like I did for the past few years in college. However, after the whole senior year doing a priori estimation for 2-d NS equation(basically frequency analysis stuff in harmonic analysis), I got nothing but fully exhausted and want to try something else where I found the machine learning course on Coursera was really interesting and decided to explore more about that in graduate school. 

I passed all qualifying exams before the first year started. I took a graduate statistics course and a computer science course in the first quarter to get a better understanding for machine learning, and found I was thrilled at high-dimensional statistics. Unfortunately there's no one in the department working in that field, so I started working with professors in the statistics department on several different projects which I really, for the first time in my life, found more interesting than I thought mathematics was in college. Now I don't feel like I will ever wish to work in any primary mathematics field, and I'm kind of alienated in the department which makes me feel sick and sometimes lonely (and often enough pure mathematicians tend to degrade statistics or applied math).

I know very clearly from the past year-long research experience with Statisticians that I am now much much more enthusiastic about high-dimensional statistics.

Should I be open to the idea of moving to a Statistics program? The only problem is that I may not be able to get a Master's degree due to departmental coursework requirement. Is it possible to transfer to another graduate program (either within University X or other university) without a master's degree from my current university? (I am pretty sure I can get quite good reference from my research professors, as well as several decent publications.)
Talk to your tutor or professor, they are there to help you and I always found mine very supportive. It sounds like you have thought about this. Find out what your options are they won't bite your head off for changing your mind. I changed direction twice before even getting to my Ph.D. then left that after 9 months when I realised it was not right for me. 

Don't spend years of your life doing something you don't care for, you will be far happier and productive doing something you truly love. There is a good chance your profs and tutors will have zig-zagged through their careers as well.