Scratch the 3D and I'd be good. It'd be difficult, but I don't doubt that Nintendo could pull it off.
Fitting the game into one DS cartridge could possibly be a challenge, although if squeezing it into one cartridge turns out to be an issue, I could tolerate it on the Wii or something. But of course, even on the Wii I'd want it to keep pokemon's classic grid-like moving etc. It could be on the 3DS I suppose, but again I'm a bit iffy on whether it could fit on one cartridge/whatever 3DS's use.
A game with every region completely detailed and a story that presumably continues through each would be pretty massive, I'm not sure how much space exactly it would require.
EDIT: Battling past protagonists could be a problem, seeing as Red would be like 30 or something when you come across him. The games aren't all happening simultaneously in each region, guys. The past main characters get older.