Borderlands...
On the PC? Quite difficult now i think about it.
Ever played Prince of Persia: Sands of Time? It has similar platforming and fighting mechanics but no stealth.
Played and completed this oneX-Men Origins: Wolverine

Chronicles of Riddick? AA intro was almost lifted from it and the combat is brutal. Well worth a look.

not played that, will give it a look
You're a lucky man, prince of persia: sands of time is one of the greatest games i've ever played. While it's not strictly the same as Batman:AA it's still a treat and a half. I wish i could play it again with no knowledge of the combat, platforming and storyline.

If you like the stealth element and nice gadgets, then Splinter cell series of games are worth playing (if you haven't already).
