Wow, they make you completely forget about those giant hawk wings, don't they?
"Your beauty is beyond compare With flamin' locks of auburn hair With ivory skin and eyes of emerald green" — Dolly Parton, "Jolene"
Green-eyed redheads are among the rarest color combinations found in humanity (with the exception of some abnormalities), and thus is used to distinguish an important, notable character visually. It's more often found with women than with men, and is almost always either found as a trait of The Hero (see Red-Headed Hero) or The Hero's Love Interest (because Heroes Want Redheads). To qualify for this trope, it's important that:
Hellsing's Pip Bernadotte, Love Interest of Seras Victoria. While he's a mercenary and an Anti-Hero to be traditionally sweet, he is the nicest of the guys in these series along with Sir Shelby Penwood. With the other men being Dracula, a deadly butler, Nazis and Fanatic Vatican Crusaders, Pip looks like a saint.
Youko Nakajima from The Twelve Kingdoms is the main character, and her red hair(which gets redder when she goes to the titular Kingdoms) marks her as different, and she is often teased for it. It also marks her as an inhabitant of the 12 Kingdoms.
Kino Makoto/Sailor Jupiter from Sailor Moon is one of the main characters and in the manga, and her hair red in color pictures, (brown in the anime). Word of God says that her eyes turn green after transforming into Jupiter, and they look more hazel/brown in her untransformed state in some artwork.
Lydia from Earl and Fairy has this as a sign of her affinity with The Fair Folk. It's a source of great trouble for her due to the cultural discrimination people with red hair suffered in Victorian England, on top of the implications she might be a changeling.
Nakaba from Reimei No Arcana is the protagnoist. Her bright red hair causes her to be discriminated against, and her green eyes turn red when she uses her powers. She's also in the middle of a love triangle between the romantic lead, and her Childhood Friend.
Jean Grey is the one of the original members of the team, the love interest of Cyclops, and took center stage in what is arguably the franchise's best known story.
Also Jean's daughter from an alternate future, Rachel, and her clone, Madelyne Pryor.
Also Hope Summers, a very important player in the X-Men franchise and obviously takes after Jean.
Fongji Wu, a mixed-race Tibetan girl and the previous bearer of both the Phoenix Force and the Iron Fist mantle.
Rogue was occasionally colored with just straight-up red hair with green eyes, especially during her most popular years in the '90s, but did eventually move to brown.
Mary Jane Watson from Spider-Man is the love interest of Peter Parker, has been a supermodel, and is known for striking good looks, as opposed to Gwen Stacy's more traditional Girl Next Door appearance (despite MJ being the literal girl next door).
Batwoman / Kate Kane, the main character of her own series, whose coloration, especially her red hair, is starkly emphasized against dark and bleak Gotham.
Lyra, daughter of Thundra and The Hulk, combines this with green skin.
Lena Luthor, at least in Supergirl: Cosmic Adventurs in the 8th Grade. Also the "Lex's daughter" incarnation in The DCU ... although in this case her green eyes may have indicated that she was still connected to Brainiac.
Lex Luthor, usually acknowledged as Superman's arch-rival, has naturally red hair (though he's usually bald for a number of reasons Depending on the Writer). So does Superman's best friend, Jimmy Olsen, and Lana Lang, his childhood sweetheart.
Caitlin Fairchild from Gen13 is this physically as well as usually personality wise (though she can be a Fiery Redhead when it comes to protecting the others).
Poison Ivy, whose coloration not only emphasizes her seductive qualities, but also seems more dangerous and earthy.
Rogue's hair is usually referred to as "auburn", but was colored more red in earlier comics. And her eyes are green.
Starfire, with golden skin. Note that while it's true that Starfire has green eyes, that doesn't mean she has normal eyes with green irises... it means her eyes are solid green.
Leetah and her daughter Ember, as well as Redlance and his daughter Tyleet in ElfQuest. Notable because Leetah and Ember are both dark-skinned.
Delirium from The Sandman is this on occasion. She can change her hair color/length at will (but mostly it happens by accident), though it usually has some red in it and is fully red at least once. Usually has one green and one blue eye, though when she composes herself and behaves seriously they are the same color.
Aphrodite in the "Adventures in Olympus" arc of Flare, notable in that the most beautiful person to exist has this combination of color, and is in fact often portrayed as a redhead in art, especially Pre-Raphaelite and Neoclassicism.
Rose in the Wolverine miniseries Origin, who is intended as a "proto-Jean Grey" in Wolverine's story, just as Dog is a "proto-Sabretooth".
Assassin, adventuress and safari-savvy Johanna Smith-Rhodes, from the Discworld continuum fanfic Nature Studies. She started life as a rather attitudinal "Sed-Efrrrrikan" with all the knobs turned up to eleven.
Mara Jade may be the ultimate example: a Badass and former Evil Redhead who was so enormously popular, she joined the good guys, became The Hero Luke's long-time partner, and was eventually happily married to him. Until Legacy of the Force, but no one likes what happened there.
Scout, the Jedi Padawan equivalent of Batman in Yoda: Dark Rendezvous, has these.
Jedi Apprentice's Clat'Ha is only in a few of the books, but she's significant in them.
Anne Shirley of Anne of Green Gables, where her hair and eye color is significant in that she personally dislikes the combination.
Lily Evans Potter from Harry Potter series is a Posthumous Character example: a formidable witch of her own, she was the love interest to James, The Hero of the previous generation, and friends with Severus Snape, until they had a falling out, but whose death became Snape's primary motivation.Fanon likes to give Ginny green eyes too, partially to hammer home the Generation Xerox point and partially out of influence of this trope, but the books establish hers as brown.
Gemma Doyle, the protagonist from the A Great and Terrible Beauty trilogy. Her mother too.
Becky Sharp in Thackeray's Vanity Fair (1847-48) is a green-eyed Evil Redhead, though her hair is probably more of the sandy variety.
Beatrice Bailey, the protagonist of The Witches of Bailiwick. Her specialty is controlling the weather, which goes with the nature aspect of this trope.
Christopher Hitchens mentioned this trope while criticizing a stereotypically Irish-American character in John Updike's last novel.
The title character of Fire is red-headed and green-eyed and beautiful beyond the lot of ordinary people; her hair and eye color both coming from her mother.
Felicity Merriman from the American Girl series, one of the few redheads who, by the nature of this trope, of course is paired with green eyes.
The Girl from The Club Dumas; her very light green eyes are mentioned many times as being captivating, likely because she is in fact a fallen angel. In the film adaptation, The Ninth Gate, however, she has different coloring.
Mildmay, one of the viewpoint characters of Doctrine of Labyrinths. For most of the story, he's one of only two-redhaired people, the other being his brother, and the only redhead with green eyes. Felix often describes them as being like jade.
A Brother's Price makes a point of noting that all of the princesses fit this trope, to the point where their hair is called "the royal red". Cira/Halley actually dyed her hair black to throw off suspicion.
Ce'Nedra from David Eddings' The Belgariad and The Mallorean, who is the beautiful, Fiery Redhead love interest of The Hero, and is part-dryad, so comes with a nature emphasis too.
Thor in Norse Mythology is a rough tough badass god, who happens to be redheaded and green-eyed. Yet when he had to cross-dress as a woman in Thrymskvida, all the giants were so smitten by "her" dazzling looks that they failed to notice many, many less-than-subtle hints of a trap...
Default female Commander Shepard is another example, whose first face model was given this coloration. Emphasizing the pervasiveness of this trope is that when a fan poll was created to choose the new look of Commander Shepard for Mass Effect 3, so many people indicated that their vote depended a lot on getting a redheaded, green-eyed Shepard with their favorite face model that the developers posted a second poll allowing people to pick the coloration, and the green-eyed redhead won by a large margin.
Aveline Vallen in Dragon Age II, is the first companion you pick up and is a green-eyed redhead. Unusually she's also one of the two companions who cannot be Hawke's Love Interest. Much of her character plot in the game focuses on her surprising subversion of gender roles, so it's possible this coloration was picked for that reason.
If you squint hard enough, you'll notice that pre-zergification Sarah Kerrigan from Starcraft series had grayish-green eyes (especially on that photo Raynor has of her in SC2), and she was a redhead.
Luke Fon Fabre from Tales of the Abyss. This is actually a plot point, as a noble with red hair and green eyes has a great role in a prophesy that will lead to world prosperity. Asch the Bloody is also a green-eyed red head, which is significant because in truth, he's the redhead from the prophesy, and Luke is only his clone.
It later becomes a plot point that Natalia is not one of these, as every blood member of the Kimlascan royal family is a green-eyed redhead.
Princess Carranya in part II of Love And War, who is the heroine and only playable female character in the episode. Whether she ends up as Ryan's love interest is strongly hinted at, but not confirmed.
Pamela Isley, a.k.a. Poison Ivy, in the Batman episode "Pretty Poison", when she uses her stunning looks to get close to the men who wronged her (one of them even proposes to her) and attempts to assassinate them.
Gotham City socialite Veronica Vreeland, one of Batman's love interests (and the only redhead amongst them).
Demona, one of the main antagonists, though ordinarily black-eyed like most gargoyles, qualifies when in human form.
Fox, recurring villain employee of and married to the other main antagonist David Xanatos.
Starfire from Teen Titans. When she's actively using her powers, she has solid green eyes like her comic book counterpart. When she's not, her eyes have are more like normal human "green eyes", but the sclera (the "white" of the eye) is also green (a paler shade than the iris).
Kiva from Megas XLR, the only major female character, the only redhead, one of the best looking characters from the show, and eventual love interest of one of the other characters.
Sam from Totally Spies!, the only redhead of the group (and the rest of the group follows typical cartoon colorations with black hair and brown eyes and blonde hair and blue eyes). She even wears green as her color!
Gwen Tennyson from Ben 10. The main female character, cousin to the main character, and a part of the most prominent love story in the series with eventual group member Kevin.
In the Family Guy episode "Road to the Multiverse", redhead Lois, whose eye color isn't usually depicted, had green eyes in the Disney 'verse (where she is meant to be portrayed in the classically beautiful way a Disney princess usually is).