I think that a free-roaming Gotham setting could work. Who really says that they have to adhere to something like GTA, restricting themselves to fetch quests and such? What do you take them for, Activision? This is Eidos/Rocksteady we're talking about. Who's to say they can't just apply the formula for B:AA into a much larger setting, tweaking it just enough so that it's still interesting?
Think about it for a moment - the next game starts. Batman's staring out at Gotham City, everything's quiet and normal. Then all of the sudden, he's told by Oracle that there are thugs beating down random civilians in the streets just blocks away. He, of course, takes to The Batmobile to take them out... but that's when he realizes that it's not just one street. The entire city is littered with criminals after a breakout at Arkham, divided into sections that supervillains have now taken over. And lo and behold, sitting in the Mayor's office is none other than Harvey Dent/Two-Face. He's taken control of the city's resources, threatening to blow up half of Gotham if he's opposed by the police. And he's not alone... villains like Black Mask, Scarface, Maxie Zues, Firefly, a returned Scarecrow, a both leaner and smarter Bane, Mad Hatter, and any other sensible boss to lead factions of an entire mob could be running the show along with Harvey. The tense atmosphere could force Batman to use Gotham's shadows to his advantage, knowing that if he gets Two-Face too worked up, he could freak and blow up half the city anyway. Batman is forced to keep his siege on the gangs as discreet as possible.
Right there, you have both a plot and a logical step up from Arkham Island's limitations. And to keep the feeling that Batman is still trapped in hell with his worst enemies, like this game did, Gotham could be cut off from the rest of society as a nod to No Man's Land. Side missions could simply be another set of Riddler Trophies, Joker bombs/toxins - or, if you really wanted to be creative, decrypted messages from the late Ra's Al Ghul, leading Batman around the city to try and stop some plot set in motion before he died. Maybe even all three! And as suggested before, they could be scattered all around Gotham without the need to bring in repetitive GTA-style missions.
My point is, don't underestimate Rocksteady's creativity with this franchise - look at what they just gave us. And if I could think up the above proposal for the next Batman game off of the top of my head, think of what they could do with months of planning and prep, not to mention Paul Dini back at the writer's helm.
