While Jonathan Hobbs is definitely correct that there is no one exact build that is going to be correct for each character, I do think there are some general guidelines we can establish: Legolas is Fey, Frodo is a halfling, Aragorn has a sword, and so on.
What you do with those guidelines is going to depend on your own personal take on the character. To make that process more clear, I'll present my personal take on each character along with some other common possibilities.
As before, Frodo is clearly a halfling. We can all agree on that.
Beyond his race though, it gets tougher, largely because Frodo isn't really all that heroic. At least in the DnD sense. That being said, I do have a suggestion:
I would focus on Frodo as a stealthy exploration rogue, perhaps with some abilities that let him turn invisible.
Although there are other aspects of the character you could emphasize, I feel that rogue makes the most sense because -- to me -- Frodo's greatest accomplishment was sneaking through Mordor to Mt. Doom. As Brian S pointed out, Frodo is not a Striker rogue. He barely participates in combat at all. Much like Bilbo, Frodo's value lies in being a little halfling. Granted, he may not sneak around quite as much as Bilbo, but as a DnD character he needs to be good at something, and if I tried to make it Mt. Doom in a 4E game, I'm pretty sure I'd make some Stealth checks. It doesn't hurt he has a ring which lets him turn invisible.
If you'd rather emphasize another aspect of the character, you might focus more on his ability to inspire his allies. Perhaps make him a bard or inspiring warlord. Frodo is also known for his ability to resist the ring's seduction and keep his head on straight, so you might focus on giving him a high will defense and fill in the other details as you like.
Gimli is a dwarf, of course, and he's going to use Martial abilities.
I would suggest a fighter would probably make the most sense, but warlord wouldn't be unreasonable. If I recall, Gimli used an axe. Don't know that there's much more there.
Legolas is Fey, and he's an excellent archer.
I would go Elf rather than Eladrin, as Legolas is from the forest, and elves are better archers than Eladrin. Obviously he's not a Drow. Elrond might be an Eladrin. We all agree Legolas is an archer, as you noted, but he can also fight well with two blades (see the Desolation of Smaug's absurd barrel scene), so a good build would probably include that capability. Hunter rangers are proficient at switching back and forth between melee and ranged combat.
Aragorn is man. He uses swords. He has both nature and leadership skills.
Aragorn does have elf heritage in the distant past (Elrond's brother), but I think the vast majority of people would expect him to be human, rather than half-elf. Additionally, Aragorn is initially introduced as the ranger Strider, not as Aragorn, the heir to a long line of kings. I feel that Strider is the prototypical ranger, and that any build of Aragorn in which he is not a ranger is 'doing it wrong'. That being said, what I really expect is for Aragorn to have good outdoor skills, so even if he's not a ranger he should have high Nature.
Another very logical build of Aragorn would be as a tactical warlord or possibly a paladin. This emphasizes his later role as the king of men over his earlier role as the ranger Strider. Maybe a hybrid?
Gandalf appears human, but he's not technically. He's a wizard, which is a sort of supernatural demi-godish being. He has magical powers, and can effectively wield a sword.
Wizard isn't a race in DnD, but there is a race of reincarnating immortals with great magical power: devas. Ignoring the physical appearance, the description of Devas in the Player's Handbook 2 sounds like a pretty good description of Wizards in LotR to me. You might also reasonably consider many other races, such as human, elf, eladrin, half-elf, a conversion of an old race, or even a home brew.
As Jonathan Hobbs pointed out, Wizards in LotR don't have the same kind of flashy spells that they have in DnD. Some of Gandalf's powers almost seem more Divine than Arcane, so perhaps a Divine class such as Invoker might make more sense. This would be in line with his own nature as a supernatural entity.
Note that Gandalf is effective in melee with both longsword and staff, so the best build would take that into account.
So there are some pretty general guidelines, along with more specific opinions. You seem like you want a specific suggestion for classes though, so here's a group of builds consistent with both those guidelines and my own opinions:
Frodo: Cunning Sneak Halfing Rogue
Gimli: Dwarf Fighter
Legolas: Hunter-Style Elf Ranger
Aragorn: Two-Blade or Marauder Human Ranger
Gandalf: Malediction or Preserving Deva Invoker