eclectician and I had talked about going down to Flushing, as he'd never been there and wanted to try some of the food. bedfull_o_books said how it was a shame that the kebab guys probably wouldn't be there. I disagreed--these guys are from Xinjiang; a little New York snow isn't going to stop them--but I promised I'd check.
They were there, in the cold, wet drizzle. I'm guessing they're there 365 days a year. They might stay home for Chinese New Year, but I doubt it.
Xinjiang BBQ kebab
41st Ave. at Main St., near the corner of Kissena Blvd.
New York, NY 11355
Subway: Main St. Flushing 
LIRR: Flushing [Port Washington Branch]
The Xinjiang kebab cart has been written up by bloggers and the NYTimes in better style and greater length than me. You can follow the links to see photos and read what they say. I'll stick to the basics.
The guy sells kebabs, on thin bamboo skewers, for a buck apiece. They're small, but this means you can sample a variety. He does lamb, beef, and chicken, all spiced with cumin and chili. Try them all.
The only variation is that he'll ask how hot you want it. Medium is a good place to start. The spicing is complex and subtle as the meat is marinaded before cooking, so you don't want to overpower everything with chili heat. Speaking of heat, they're cooked to order so they come right off the coals. Don't burn your mouth, even though their wonderful aroma will make you want to start eating them before they're cool enough.
All of the skewers are $1 each. He's been there every time I've gone by, but I imagine he probably closes up after foot traffic dies down at night. Lunch to dinner is a safe bet for hours. Finding him is easy; the corner of Kissena and Main is just south of the LIRR tracks. If you're on Main St. you can't miss the smoke.
He has a bunch of competitors on nearby street corners, some north on Main. Accept no substitutes. This guy is the best.