As fun as discussing biographies alone could be, I'd like to mention one major aspect you'll need to infuse them with. This is an aspect that the last few reworks failed badly with, and is especially a reason why nobody likes Ashe anymore.
That aspect is player immersion.
Player immersion is generally an aspect specific for people who enjoy the game's lore, because they are the ones who like to live in the game's world a little. People who play the game for purely gameplay reasons don't care and won't start caring; they wouldn't have shorthands for champions with long names if they did, neither would they refer to skills entirely by their hotkeys instead of names. But to players who want to immerse themselves, such as lore junkies, it's important to create a small window that allows them to enter the world through that champion.
In the past, that immersion was provided entirely through the summoner-themed GUI. Now it will need to be provided through the characters themselves, as associating themselves with the characters they currently play is the only remaining window for players. Here is an example...
Her old lore provided both opportunities for immersion. As a summoner, I would like to support a major and well-respected political leader who is leading her third-world country onto the global scene. As Ashe, I'm the badass queen who may not have much power on her own but I can lead my team to victory with a well-placed word, a dash of utility and a helpful arrow across the map. Both of those are cool angles...
Now her new lore is... basically a cowardly King Arthur. That could still be a decent immersion angle for a summoner because it means they're supporting a young and inexperienced queen with whose ideals they agree, and hope she'll grow through their guidance. On the other hand, associating yourself with this Ashe's character is just... not very fun. She's flimsy and kinda incompetent and there is no reason to really want to be her. She is a huge failure on that regard.
With that in mind, let's look at the champions you mentioned.
His lore will likely need a complete overhaul. A mystery wrapped inside an enigma is just not much for a player to associate with. While the old Jax was fun to play from the summoner angle because you were essentially radio support and drinking buddies for this unstoppable badass who is cocky but lovable, from the point of self-association, he is a complete blank slate. There's nothing going for him.
For the sake of a rework, I would recommend looking at Wolverine from Marvel Comics. You'll probably want a character who is somewhat mysterious in that only shreds of his past are known (just enough to connect the dots into a vague outline, but not a complete image), whose experience shows through his lines and actions, and whose lack of association with specific factions is made up for via numerous connections with people here and there. Essentially, turn him into a gruff, weary guy who everyone knows and either fears or respects. I know people brought up making him an arena fighter or a mercenary, but I think he'd flow smoother as a vagrant who'd been both but moved on to other things.
Overall, he's much easier to associate yourself with because he's a very "normal" guy, so let's talk story. A lot of people are attached to his summoner past, so you might want to rework him alongside another mage character. Making him someone's failed apprentice who moved on after a terrible failure is one good angle. Maybe claim that he's the one who summoned Nocturne in front of many people, and is out to atone for his old actions?
Oh, and you'll need to look into his old history with the Noxus vs. Ionia war. Like many people said, that war makes no logistical sense right now. Basic tactics 101 dictate that Noxus should've been wiped off the face of the planet during it.
EDIT: I thought I'd continue in part 2, but there's a perfectly fine Nocturne discussion thread that I'll chip into instead.