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, her hair which is brown in the anime is more red in color pictures. 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.
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.
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.
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.
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.
In Teen Wolf Lydia Martin. She walked away from the bite of a Alpha Werewolf alive and human. Managed to resurrect said Alpha Werewolf and then broke the Kanima curse on her boyfriend. She is a supernatural creature herself, a banshee, also known as The Wailing Woman.
Sleepy Hollow has Katrina, a red-headed, green-eyed witch. Actress Katia Winter is not a natural red-head, so this trope is in effect.
In Dolly Parton's song "Jolene", the titular character (and the narrator's romantic rival) has "flaming locks of auburn hair" and "eyes of emerald green".
William Sheller's song "Les miroirs dans la boue" (The Mirrors in the Mud) is all about a young girl with "green eyes bathed in red hair" ("les yeux verts noyés de cheveux roux").
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...
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. 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.
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).
Raphael in Teenage Mutant Ninja Turtles (2012) is given green eyes that go with his red bandana as a subtle nod to this trope. Similarly Michelangelo is given blue eyes to go with his orange (read blond) bandana evoking a similar common phenotype in ficion.