The left boot is off. The shirt went two hours ago. Having signalled the end of the previous song by ricocheting his microphone off the drummer’s bass, the man whose haircut is half-quiff, half-mullet, but whose moustache is all pantomime genie, hoists himself from stage to balcony. Now several feet above the 500-strong New York audience, he conspires to crank the frenzied atmosphere even higher, brandishing his acoustic guitar like a semi-automatic weapon and yelping a mangled mix of Ukrainian, Russian and English. Around his sticky torso hangs the flag of the Romany people. On stage, fire buckets are being used as percussion. A Russian man of pensionable age plays the fiddle while another bashes an accordion. It’s a fantastic racket; one that combines elements of folk, flamenco, ska and Balkan gypsy music, played with the gusto of punk, performed with the flamboyance of cabaret.

The band are Gogol Bordello. The frontman is Eugene Hütz, a 34-year-old Kiev refugee. Gogol Bordello call themselves a "global collective" and they number an Israeli guitarist, an Ethiopian bassist, an American drummer, the aforementioned Russian accordionist and violinist, plus Thai-American and Chinese-Scottish percussionist-dancers. Their nearest precedent may be the Pogues – the up-for-it gang of ne’er-do-wells whose genius was to unite traditional Irish folk with breakneck punk rock. But Gogol Bordello’s act is more singular still, so much so that Hütz has been compelled to christen a new musical genre – "gypsy punk" – provocatively suggesting his band’s combustive effect on audiences as “like a porn magazine being thrown into a kindergarten”.

“Last night was extra-crazy, man,” Hütz says over dinner following the first of two long-since sold-out nights in New York, somewhere as much as anywhere he now calls home, having formed the band here in 1999 following a journey out of the Soviet Union, across Europe and into America. “It was retarded. I guess we have shaken up quite a bit of apple carts all over the place and that we have made people confused and started many arguments. When people see us the first time they see two or three songs and they go, ‘No f****** way.’”

Their effect on Gogol Bordello virgins might be as bafflingly endearing as Hütz’s own seesawing accent, liberal use of expletives and cavalier approach to grammar, but for a band four albums into their career who’ve relished their underdog status, they’ve reached a kind of tipping point.

Back in July, Gogol Bordello found themselves with exposure of the biggest kind imaginable: being introduced to an audience of two billion, when Hütz and violinist Sergey Rjabtzev performed with Madonna at Live Earth (“I’d like to introduce my Romany gypsy friends…”). Little matter that a noisy Romany reworking of La Isla Bonita presented those watching with something of a challenge, it was another milestone on his charismatic road to stardom. “I had all these gypsies calling me from Russia and Ukraine going, ‘I can’t believe you got Madonna singing the Romanesse.’ It was like a new chapter for everybody. The whole thing came in an idea just a few days before Live Earth itself, you know? It turned into this major publicity stunt.”

Hütz is no stranger to the bright lights. In 2005’s film adaptation of Jonathan Safran Foer’s novel Everything is Illuminated – the tale of an American who travels to Ukraine in search of his Russo-Jewish roots – Hütz upstaged Elijah Wood in his role as Aleksandr ‘Alex’ Perchov, earning praise all round. Hütz and Wood remain friends, with music-nut Wood dating Pamela Racine, one of Gogol Bordello’s dancer-percussionists.

And Hütz was recently the subject of a documentary, The Pied Piper of Hutzovina – just out on DVD – which follows him on a pilgrimage back to Eastern Europe, where he fails to convince the head of the Kiev Gypsy Theatre that his latest musical innovation, ‘gypsy hip-hop’, has legs.

After touring the UK in December, we’ll see him in his second acting role, as the lead in Filth and Wisdom, a low-budget comedy that also happens to be Madonna’s directorial debut. “Eugene’s charismatic madness is hard to resist,” Madonna explains. “I like him because he has suffered, because he reads books, because he is authentic.”

I first meet Hütz 24 hours earlier. He has his head in his hands and his feet in a bin. It is the afternoon before the first New York show and Gogol Bordello have not long arrived from Philadelphia. “I totally overdid it last night,” he groans. “But it will come back.” Slowly, it does. At Irving Plaza, tonight’s venue, Gogol Bordello are photographed for L’Uomo Vogue – the King James of fashion bibles. The Italian title’s OTT sensibilities turn out to be a good match for Gogol Bordello’s rag-tag aesthetic. “We want to show their heart and soul, but make it more so,” explains Rushka Bergman, L’Uomo Vogue’s fashion editor, a commanding woman in a Balenciaga ballgown and diamond-encrusted gladiator sandals.

Hütz isn’t new to the fashion world. He spent two years as a model, signing with an agency when he arrived in New York and found gainful employment with Marc Jacobs and Donna Karan among others. “Catwalk, photos for magazine, I did it all,” he tuts. “Back in my retarded mode when I was thinking about becoming a fashion designer.” He quit “as soon as I could replace money from there with my music money”. Still, he’s always cultivated a look; cutting the arms and necks off T-shirts and sewing patches over everything. It would be a mistake, though, to confuse facial hair with fashion statement. “There is saying in Ukraine that a man without a moustache is like a woman with one,” he explains. “I strongly stand behind that theory.”

Growing up in a Kiev tower block, space was at something of a premium. “There was nine of us,” says Hütz. “My grandfather lived on the balcony. In winter, he would usually split somewhere else.” Hütz’s mother was a dancer and a singer, his father an occasional guitarist and local butcher. An army training in radio technology meant that Dad could unscramble the blocks Soviet authorities had placed on Western signals, and by his early teens, Hütz was straining to enjoy the Doors and Jimi Hendrix through the static. Since everybody wanted to be friends with the local butcher, Dad was also able to trade meat for cassettes of more esoteric treasure. The Birthday Party – Nick Cave’s challenging first band – proved inspirational. “I felt that it’s absolutely insane and magnificent and on the other hand, I can play shit like that! You didn’t have to be Emerson, Lake & Palmer, you know.”

At 18 he left home to work his way round Europe and eventually ended up in New York, before starting to trade explicitly on his gypsy roots (his grandmother is Roma) and forming Gogol Bordello, naming them after the Ukrainian-born author of offbeat Russian tales, Nikolai Gogol. He’s now a champion for his heritage. “Most of the gypsy, if you meet them, they will deny their nationality,” he says. “It’s not a terrible thing, it’s just a survival tactic, you know?”

Soon, Gogol Bordello were the talk of the Downtown scene. “It was late Nineties and New York felt like it was about to fall asleep. We come with the live chickens and whatnot. A lot of crazy shit, like 30 people on stage. Everybody swinging on chandeliers. The whole crowd dancing on the bar at the end of the show. Banned from every club in town. It was mayhem.”

Hütz is a fan of the Clash and some Gogol Bordello songs are overtly politicised, such as Greencard Husband from 1999’s Voi-La Intruder or Think Locally, F*** Globally from 2005's Gypsy Punks: Underdog World Strike. Other times, meanings don’t arrive so easily. “I’m still trying to figure that song out,” says Hütz of Super Theory of Super Everything from this year’s album Super Taranta!, out now.

Filth and Wisdom should be just as intriguing. Co-starring Richard E. Grant, it features a ballet school, a dominatrix and Hütz in drag. “Sure. Every actor dreams of a role like that,” he says of the film that debuts at the Sundance Film Festival in January. “Let’s not forget who direct it.” Was Madonna a good first-time director? “I was impressed. She’s a very hard worker but so is me.” Maybe she had some pointers from her director husband? “I’m not really supposed to talk about it a lot,” he says. And anyway, it’s not like he’s planning to act full-time. “Acting is tedious as f***. Why would I change my career even? Music is love of my life.

“I think I’m in a place where I want to be and that’s pretty great, you know? But I don’t analyse it all that much,” he continues. “For the most time I’m driven by complete instinct.”

Explore Music

• Festivals

• CD Reviews

• Live Reviews

• Classical

Editor's choice

• U2 at Nou Camp Stadium, Barcelona
• The 50 Best Movie Villains
• The 15 golden rules of theatre etiquette