I guess the first question you should be asking yourself is: "is this a sincere recommendation"? What are your personal characteristics/skills that make you a suitable student for the TA position? That is a similar dilemma you will face if you join the corporate job market in the future. If you had interesting achievements in Prof X's course, and you stood out for whatever reason, I think it is perfectly valid to state your desire to have a recommendation.
If you are going to aggregate a hell lot of value for Prof Y, he will be truly glad that Prof X suggested your name, pointing out the characteristics he previously observed.
On the other hand, if you do not feel like you have much of a track record to justify a recommendation, I guess the best approach might be to directly contact Professor Y and state your interest. Remember to put yourself in the shoes of your boss-to-be: Professors usually have hectic routines, and they will love you forever if you are able to make them forget the operational, boring activities of the courses. They will have extra time to plan their lectures and produce scientific output.
tl;dr: "Ask yourself: what are the characteristics that will make me super useful to Prof Y? If you do not have them yet, what does it take to learn them?"
If, after this exercise, you would recommend yourself, go for it, ask for the recommendation!