However, all going well, there will be some new material too.
Though Clement, talking to TimeOut from New York last week where he was attending the Men In Black US premiere, is a little coy about what shape the new songs are in - and what they are about.
"They're just ideas. They might not make it," he says. "We normally play things once, and then never play them again. But there is a father and son song, where I play the father and Bret plays the son. Then there's one where I play a lady and Bret plays a man. And we're trying to do a German kind of one too; we've never made it through that song, but we'll try."
As well as writing new tunes they are also rehearsing - hard - to get the old songs up to scratch.
"The ones that we have been playing a really long time, they are no problem, but it's some of the ones we played on TV [series Flight of the Conchords], which we didn't really play live, they are the hard ones."
And the Conchords haven't played live for a little while either. In 2010, off the back of the success of their TV show for American cable channel HBO, they played the 17,000-capacity Hollywood Bowl in Los Angeles and a sell-out show at the 12,500 capacity Wembley Arena.
The last time they played in New Zealand was a fundraiser in March, 2009, for Masterton's Makoura College, Clement's old high school. The 2000 tickets sold out in 90 minutes. Before that they performed a free show in February, 2008, at Wellington's Aro St Video store to celebrate winning the best comedy album Grammy for their EP The Distant Future.
The clamour for tickets when the latest tour was announced - with all of the initial shows selling out in minutes, including a 10,000-capacity Vector Arena show with a second being added - surprised Clement.
"I was interested to see how it would go. And we'd booked Vector, you know? When I saw that, I said to the people organising it, 'I don't think we're going to fill the Vector'," he chuckles.
He's a little nervous about both his biggest film role yet and the Conchords' biggest concert tour to date.
"The film is over in a matter of hours," he says with a laugh. "The tour though, we'll only be nervous for the first one.
"Touring's really fun. That's the funnest part of all this. But then after about a month and a half both Bret and I get a bit tired of it. Some people do it for a year, and then they have a couple of months off, and then they go again. And that's fine."
But not the Conchords; come the end of the Australian dates in Perth (two sold-out shows no less, with a third added), they will be on to their next projects. That's the thing about Clement and McKenzie, while they are partners in crime they are also self-sufficient. Clement reckons this is the reason the Conchords have stayed together since forming in Wellington in the late 90s.
"That's what has always kept us going. We've always had our own thing. Even when we started I had my other comedy duo [The Humourbeasts, with film director, long-time collaborator, and friend Taika Waititi] and Bret had his other band the Black Seeds. We always had at least one thing that we could do to have a break from doing this."
Though there is the possibility of a Conchords' feature film, in recent years the pair have mostly been going it alone. Earlier this year McKenzie won the best original song Oscar for Man or Muppet, and has upcoming roles in local feature Two Little Boys and The Hobbit.
Meanwhile, Clement has had a string of small, oddball film roles. These have included voice parts in Despicable Me, and Rio, as slightly creepy fantasy writer Dr Ronald Chevalier in Gentlemen Broncos and very creepy artist Kieran Vollard in Dinner For Schmucks, before hitting the big time as Boris in Men In Black, which opened around the world last week.
He is also currently working on a vampire movie with Waititi, which will be shot in Wellington, hopefully before the end of the year, and he's enjoying being back writing after a long, badly needed break.
"We finished [Men In Black] in October last year, and I've been doing a lot of writing since then. I was doing a lot of acting to get away from writing, I was struggling to think of things at times, so I needed a rest from it and I'm glad I had something else to do.
"But I'm back into it and I'm just really happy to be doing it. So Bret and I have been writing songs, a screenplay with Taika, and I have another TV idea I'm working on with some other friends of mine. But I haven't been pushing it too hard."
He's a hard man to track down though. Getting him on the phone took almost two weeks to nail down, and then on the day of the interview he went missing. However, when TimeOut finally got hold of him in New York he was apologetic.
"I'm so sorry. Actually, what I was doing was trying to sort out my clothes [for the premiere]."
Though the big-budget Men In Black was a far larger production than the Conchords' TV series, working on the film brought back fond memories because both were filmed in New York in areas such as Chinatown.
However, Clement did have a few nerves about playing a ruthless villain.
"There's a bad guy in all of us but my concern was how bad a badass I would be," he said. "I wasn't convincing myself for a while there. But then they put the leather suit on you, and the shoes, I had these three-inch high heels that made me infinitely taller than everyone else, and this scary makeup and you could see the way everyone was reacting to it. They were horrified, and they'd walk away. So I knew there was a bit of power there. That was good for the confidence."
The role of Boris is even more impressive given Clement is in the film almost more than original cast member Jones who plays Agent K. If anything, the Kiwi actor, who channels Dr Ronald Chevalier, Mick Jagger, and the Wilberforces to come up with Boris' frighteningly polite yet evil accent, would have liked to have told a few more jokes.
"I thought it would be more jokey, like the first Men In Black film. The baddie in that was really funny. And when they asked me to do it I thought it would be like that instead of just like scaring people."
Still, and perhaps not surprisingly, Clement admits life is good.
"I'm pretty well blessed at the moment."
THEIR GLORIOUS CAREER
1996
Jemaine Clement and Bret McKenzie meet at Victoria University, Wellington.
1998
Flight of the Conchords formed.
2000
Perform at the Canadian Fringe Festival.
2001
McKenzie appears in The Lord of the Rings: The Fellowship of the Rings. Though a small part, fans dub his elf character Figwit.
2002
Perform at the Edinburgh Fringe Festival in small underground venue called The Cave.
Release live album, Folk the World Tour.
Clement stars in local martial arts comedy Tongan Ninja.
2003
Return to Edinburgh Fringe Festival. Once again playing The Cave.
McKenzie apears in The Lord of the Rings: The Return of the King.
2004
Play sold-out show at Edinburgh Fringe Festival.
Due to the show's success they sign up to make a six-part radio show for BBC which features Rob Brydon and a cameo from Neil Finn, among others.
2005
Move to London to write and record radio show about their search for success in London, which is a forerunner to their New York-based TV show. Also stars Rhys Darby as band manager Brian Nesbitt.
Invited to Aspen Comedy Festival. Bigwigs from HBO ask them to record a half-hour performance for American comedy show, One Night Stand.
2007
Clement plays Jarrod in director Taika Waititi's debut feature Eagle Vs Shark.
Release The Distant Future EP. Wins best comedy album Grammy.
HBO TV series Flight of the Conchords premieres in the US.
2008
Clement and McKenzie star in local horror comedy Diagnosis: Death.
Release debut album Flight of the Conchords. Win album of the year, best group, breakthrough artist, and international achievement at the NZ Music Awards.
2009
Second series of Flight of the Conchords starts in US.
Release second album I Told You I Was Freaky.
Clement plays Dr Ronald Chevalier in Gentlemen Broncos.
2010
Appear in an episode of The Simpsons
Clement voices Jerry the Minion in animated feature Despicable Me; plays Spook in Predicament; and Kieran Vollard in Dinner For Schmucks.
Conchords tour US and Europe, including playing the 17,000-capacity Hollywood Bowl in Los Angeles and selling-out the 12,500 capacity Wembley Arena.
2011
McKenzie films the Robert Sarkies-directed Two Little Boys (to be released in NZ late 2012).
Clement voices Nigel in animated feature Rio.
2012
McKenzie's Man or Muppet wins Academy Award for Best Original Song. Also plays Lindir in The Hobbit.
Clement stars as bad guy alien Boris the Animal in Men In Black 3.
LOWDOWN
Who: Jemaine Clement from Flight of the Conchords and Men In Black III's resident baddie Boris the Animal
What: Men In Black III, in cinemas now
Where & when: Most dates for the June tour have sold out but there are still tickets left to the Vector show on June 29 and the third Michael Fowler Centre concert in Wellington on June 21.
More info: flightoftheconchords.co.nz.
-TimeOut
