Joanna Newsom, Royal Festival Hall, London

When Voltaire said it of God, there was something about the line "if [he] didn't exist, it would be necessary to invent him" that inspired a debate that continues to this day.

Which makes it all the sadder that his words have now been paraphrased to within an inch of their life by anyone looking for a lazy cliché. Worse, it's a cliché generally used to describe people we have neither the language nor the imagination to invent.

The thought springs to mind after Joanna Newsom's exquisite concert in London on Tuesday night. Who would have thought that there was a gap in the market for a singer-songwriter who writes poem-songs that stretch to the 10-minute mark and beyond, who knew she wanted to play the harp before she was old enough to hold one, and who is as inspired by Renaissance music as she is by Appalachian folk, west African rhythms and ragtime jazz?

So if there are the markings of the mythological around this 28-year-old Californian, it should come as no surprise that she slinks on to the stage in a pearlescent gown with a sea-shell belt looking like a cross between a mermaid and an abandoned bride. She opens, just the harp for accompaniment, with "'81", from her recent triple album Have One on Me. In its unusually short running time of under five minutes, Newsom sings of tilling the Garden of Eden, St George and the dragon, the secession from the union and lying by a spring "as naked as a trout". It is in many ways a typical piece. It is greeted by reverent hush and then euphoric applause.

Newsom is then joined by her band – a drummer/percussionist, a guitarist as adept with a Bulgarian tambura as he is with an array of reed and wind instruments, two violinists and a trombonist. The set draws heavily from Have One on Me and, as Newsom shifts to the grand piano, she warns the audience that when she goes back to the harp, it will require some tuning and that void will be filled by an audience Q&A session presided over by percussionist and arranger Neil Morgan. Cue one of the strangest and, in Morgan's words, "most psychedelic" interludes this hall will ever witness.

Questions range from "Why don't you like cheese?" (answer: "You must have been at the last show; I have nothing against cheese") to "If I give you a CD of my music, will you listen to it?" (answer: "Yes") to "Will you marry me?" (answer: "No") to "What do you think about the pedestrianisation of Norwich city centre?" (no answer).

When Newsom is done tuning, she declares, as only she would, the harp a "persnickety" instrument, before casting her spell once more over the 3,000 or so present. And while the odd song collapses under the weight of its ideas, for the most part symphonies swirl, motifs that others would build a career out of drop in and out and no one can be left in any doubt that they are witnessing a master at work.

A version of old favourite "The Book of Right-on" is so mesmerising that even the guy sitting next to me, who has given the odd shuffle in his seat and has clearly been dragged along by his female companion, turns at the end of the song to ask me its title. Newsom's main instrument, her voice, can still polarise opinion, but it should be noted that since an operation on a vocal-cord nodule last year it has become a far sweeter instrument – as likely to invoke Joni Mitchell as it is Björk.

In a recent interview, Newsom expressed her disappointment at the way the public has embraced Lady Gaga, saying, "There's not much in her music to distinguish it from other glossy, formulaic pop. She just happens to wear weirder outfits than Britney Spears." It's a telling and perceptive comment. Because for all the female artists battling to be crowned the new "Queen of Pop", Newsom, for all her inherent quirkiness, is probably the one making the records that will best stand the test of time and most challenge our lazy perceptions of what "pop" music is and can be.

From kooky curio to concert hall in six years. Joanna Newsom. If she didn't exist, we could never invent her.

Joanna Newsom headlines the Green Man Festival on 22 Aug, www.greenman.net