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:
The character isn't from a live-action work, unless they were artificially given these colors for the purpose of the work, or were chosen directly for it.
The character has red hair and green eyes, and not pink/magenta hair or hazel/blue-green eyes, or even green hair and red eyes.
Kurama, at least in his human form, but only in the anime. The crimson hair/leaf-green eyes combination in this case is a warning not to underestimatehim, because, like his roses, he has thorns. It's also possibly a hint at his youkai nature, because it's a decidedly unnatural shade of red for a human.
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.
Jean Grey from the X-Men 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 her daughter from an alternate future, Rachel, and her clone, Madelyne Pryor.
Also Hope Summers, a very important player in the X-Men franchise.
Fongji Wu, a mixed-race Tibetan girl and the previous bearer of both the Phoenix Force and the Iron Fist mantle.
Mary Jane Watson from Spider-Man is the love interest of Peter Parker.
Maxima from Superman has the red hair and green eyes.
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). Incidentally, so does Superman's best friend, Jimmy Olsen.
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.
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, 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.
Fan Works
The Pokemon fanfic CloudedSky has all of the people on Tobias' homeland Waytar with red hair and green eyes.
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.
Julia Carlyle, from the Daria/Legion Of Super-Heroes crossover Legion of Lawndale Heroes, has dark red hair and green eyes.
Mara Jade from the Star Wars Expanded Universe 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.
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.
Cherry Valance from The Outsiders is the redhead with green eyes that starts all the trouble in the book, while allowing Ponyboy, the protagonist, to change his view on Socs.
In Michael Flynn's January Dancer, a woman is introduced by her red hair and green eyes even before her name is given.
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 The 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.
The Hot Witch from Oscar Wilde's "The Fisherman and his Soul"
Music
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").
Gaelic Storm's Green Eyes, Red Hair is all about this. The woman in question overlaps with Fiery Redhead too.
Mythology
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...
Tabletop Games
Of the pantheon worshiped by humans in the Forgotten Realms, the green-eyed redhead, Sune, is the freaking Love Goddess.
Video Games
Talia Maurva from the Aveyond Series has red hair and green eyes, and is a talented magic wielder.
The Bridge Bunny Kelly Chambers in Mass Effect 2 is probably the most trouble-free and relaxing romantic interest (for both genders). Don't expect any ass-kicking from her, though.
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.
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.
Saya Kho in the X-Universe series. Red hair, green eyes, spectacular body, and she started a war that eventually resulted in the entire jumpgate network shutting down.
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.
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).
Doubly Subverted with Ms. Martian. She's a shapeshifter who based her humanoid appearance off a character from a sitcom, but her green eyes are actually a case of Morphic Resonance that she keeps in whatever form she's in.
Gosalyn Mallard from Darkwing Duck, although the fiery still comes through loud and clear.
Prototypical TJ from Recess was this. In the final product he's a brunette and has typical, cartoony black eyes.
Valerie Frizzle from Magic School Bus. Though in the cartoon and book series she, like the kids, usually has typical cartoon eyes, we do get to see her eye color in one book: Explores the Senses.
A male example, Dr. Krieger from Archer is red-headed, as well as the only green-eyed main character.
