Well, in a slightly different order than you presented, I would envision him doing The Recent Song first, then The Interesting Collaborative, and then ending with The Classic.
My choice of song selections would be for him:
The Recent Song: "Days" with him strumming his accoustic guitar. A slow, serious song to show off his versatility and to captivate the crowd in anticpation of what he will do next.
The Interesting Collaborative: "Can You Hear Me" with Sheryl Crow (although I supposed she is in France now with b/f Lance Armstrong for his final race). I don't know...I just envision Bowie and Crow performing together, as I think they will mesh well together. Not only that, but the song's title and them could be an alternate take instead of being a love song of being a song fitting for the occassion...to make voices be heard.
and then finally...
The Classic: Why, "Heroes," of course. Yes, it is a bit cliche, but it is a timeless classic, can be delivered as a song with a message, and like every other tribute performance before (including Live Aid), it is his standard.
Now, as far as this presently "non-existent" band of his goes, I don't know why he can't simply call up Gerry, Earl, Mike, Gail, Sterling, and Cat. And if some of them indeed aren't available, you can't tell me that he never had backups waiting in the wings just in case. And where's Carlos? Where's Reeves? Geez, where is Mark Platti...you know he always LOVED being in Bowie's limelight and would have loved a piece of this action just to have his stage presence be known (yes, as you can tell, I don't care for Mark too much)!
Ok, now I am ranting and rambling...
"Monday, Tuesday, Wednesday born I was..."