Let the shuffle gods decide: Will Oldham lets his iPod do the talking

We have a date with destiny but Will Oldham is walking out of his central London hotel just as I'm going in. "Gonna get a better cup of coffee than they serve here and I'll be right back," he says, strolling out on to Tottenham Court Road. Twenty-five minutes later, Oldham returns. He is not, it seems, a man to take his beverages lightly.

This is hardly surprising. If one thing has characterised the 38-year-old's life till now it is a wilfulness bordering on the abstruse. He quit high school in Louisville, Kentucky, to study drama and bagged the part of a boy-preacher in John Sayles' 1987 film Matewan. He went back to studying, dropped out of the Ivy League Brown University in New England, and then landed a plum part in the made-for-TV drama Everybody's Baby, the story of Jessica McClure, the little girl who fell down a well. (He played her dad.) A handful of minor roles later, Oldham was already heading off in a whole new direction.

He had always had connections to the Louisville music scene. His older brother Ned had played in local bands, and a photograph Oldham had taken had been used as the cover shot for Slint's 1991 album Spiderland. Still in his early twenties, Oldham picked up a guitar and, because he had grown up around the DIY punk ethos, started making records with his friends. At first, these records were released by acts with names such as Palace Brothers, Palace Music, Palace Songs and, sometimes, plain Palace. One – 1996's Arise, Therefore – was put out with no name on the packaging at all. The idea was that Oldham could disappear into a musical persona: a country-outlaw troubadour with a face to grace Mount Rushmore.

Since 1999, he has settled and grown into the name Bonnie "Prince" Billy. But while it's now easier to find and listen to his music, there is no more logic in the way it is released. Records come out whenever Oldham feels like it: there have been two recent live albums, one guitar-heavy and abrasive, the other with the Scottish folk troupe Harem Scarem. In 2004, he released Bonnie "Prince" Billy Sings Greatest Palace Music, a collection of his favourite Palace songs rerecorded with a group of polished Nashville session musicians.

He still acts occasionally too: Junebug and Old Joy are recent high points. And, slowly, Oldham has grown into the sort of artist that, as it did last month, The New Yorker would devote six pages to. (His mother, when asked for an opinion on her middle son for that piece, chose "ornery" [stubborn] as the word to best describe him.) Johnny Cash covered him. Björk has collaborated. The anti-folk singer Jeffrey Lewis has a song about a hallucinatory meeting with Oldham on the New York subway (it's called "Williamsburg Will Oldham Massacre" and the video on YouTube can't be recommended highly enough).

But what was that about a date with destiny? It goes without saying Oldham doesn't much like interviews. In fact, he is threatening to never give them again and is only doing so now because his new record is as approachable, warm and inclusive as he is ever likely to make. Perversely, and therefore naturally, it's called Beware, and so we have decided to throw caution to the wind and let the fates decide what we will talk about today. Oldham's knowledge and love of music runs deep. So, armed only with the 10,461 files on his 80GB iPod –the stuff that he is "most into, most wants to be into, or most wants to learn from" – we plan to put our conversational destiny into the hands of the "shuffle" gods and see what happens. Think The Dice Man – only with songs in place of sinister possibilities...

John Parish and Polly Jean Harvey

BPB: "Let's hit the button. Well, the first song that comes up is 'City of No Sun' from the 1996 album Dance Hall at Louse Point. When this came out I thought it was a really great record. I still think so. Vocally, it's one of the most exciting records in the past decade. There's whispers and sometimes there's screaming. [Sings] 'Love me tenderly my darling/...In the city of light and truth'. I've never tried to figure out why she sings the way she does or the intent behind it, but I guess there's a villainous aspect to it."

The Pipil Indians of El Salvador

"This next song is called 'El Barrenar'. The Smithsonian library has a website and you can order anything from the archives. Someone will then burn you a CD. I was going to El Salvador a year ago and I wanted to hear some music in the months leading up to my trip there. This is vocal, rustic and is in Spanish, when I was hoping it would be in an American-Indian dialect. It's probably from some time in the 1960s. The truth is I'm not all that happy with this purchase."

Unknown artist

"This is better. It's called 'Wexford Mummer's Song' and it's from a record called As I Roved Out, a compilation of Irish field recordings collected by Jean Ritchie and George Pickow. The principal appeal of this song is being able to hear what Ritchie was into and collecting. You can hear people talking and laughing in the background. Though I've been to Dublin many times, I don't much like cities. I don't like the idea of being surrounded by hidden things; people you can't see in buildings and cars. Cities are made for enemies to destroy."

Pupu Himene

"This next song is Tahitian. It's from a record called Polynesian Polyphonies that features a choral music called himene. It's Polynesian hymns, probably Christian in theme. Whenever I see something that looks like it could be good – whether it's on vinyl, CD or cassette – if it's not too expensive, I'll take a chance."

Timbaland

"We now come to 'Boardmeeting', one word, by Timbaland featuring Magoo from his 2007 record Shock Value. I have never listened to this song. I was on tour and I watched a Timbaland video with Nelly Furtado late one night on the hotel TV. I liked it and thought, OK, I must listen to the rest of the record. But I don't like the rest of the record, though I should at this point confess a weakness for Nelly Furtado records in general."

Joe Walsh

"This is 'Midnight Visitor' from Joe Walsh's 1972 record Barnstorm. It's a recommendation from a friend who randomly called and said he thought I'd love it. He'd never recommended music to me before. It's like psychedelic folk and I like Walsh's voice a lot."

Roy Acuff

"Here's another singer I love. This is 'Wreck on the Highway', it's a pretty standard American folk-country number sung by a man with an incredibly expressive and unique voice. It's a cool story song; a factual, pretty violent and gory telling of a wreck on the highway. The refrain is [sings] 'All that blood... all that blood/ But I didn't hear nobody pray, I didn't hear nobody pray.' It's a classic, for sure."

Cat Stevens

"This last one is 'Randy'. It's from Back to Earth [1978], Cat Stevens' last record as Cat Stevens, which has a really beautiful cover of a waterfall – like a long exposure, so the water looks like a solid white stream. On the back it already had, I think, the name of god in Arabic. After a couple of strange and unsatisfying records I felt like this was super-great, although 'Randy' is not one of my favourite songs on it. What's it about? An elephant? A woman? A dog? A boy?"

With that mystery hanging in the air, Oldham mutters something about being able to do this all day. Next up on what may or may not be his last-ever round of UK press, is a journalist from the NME. Then, Oldham will go back to Kentucky to do whatever he pleases. Just before he left, I asked about the title of his new record. Of what, specifically, should one beware? He answered: "Not liking this record very much." And you can make of that – and everything else Will Oldham-related, for that matter – what you will.

'Beware' is out on Domino tomorrow. Bonnie 'Prince' Billy plays the Royal Festival Hall, London SE1, on 20 April (0871 663 2500)