Now, concerning new material...
El Dorado can't really be set as an example for a new song that was premiered first live and then on record. Maiden put it on the website one day before tour started.
Wildest Dreams on the other hand could be a good example. A best of tour announced late autumn in '02, followed by Maiden going to studio Jan - Mar '03, tour starting May '03 which premiered song that was officialy released as a single in Sep '03. I could easily see same scenario happening.
Also, when I say single, I don't really mean actual single per se, like in actual physical format (on CD or vinyl) that could be sold. It could just be new song, released on Youtube or some other media service. Look at the Last Chapter, the whole Book of Souls deal is over, you can buy the audio, but the video is on their Youtube page completely free. It could be that Rod and the managemant sensed it would be more usefull putting on some things for free so they could sucess in some other areas (for example, something new released this May via their webpage to lure the people that are still on fences about the tour).