The Shinji ending up on a starship approach does have potential on it's own, being on a vessel full of misfits on a mission to find his homeworld and eliminate Angels. To do it right however requires writing a lot of OCs very, very well. Well enough you don't mind the absence of the Eva characters. Not impossible, but difficult. The politics involved would be very alien and yet very human, and of course you get to examine Shinji really and truly on his own having to deal with these things and grow to face them.
The other approach, Earth being contacted first, makes it a bit easier and harder in some ways. I imagine the UN would want the Eva pilots to represent humanity in a positive way - To that end, they'd try to meddle directly in NERV's operations (since SEELE does not have complete and total control over them). When it comes to the Angels the conventional military and government have to rely entirely on NERV - In this instance they might have more leverage given they possess resources NERV would need for liftoff, people who would function as diplomats and translators, not to mention people trained in space operations that NERV would need but the UN would only give up in exchange for certain favors. NERV, however, would be the representatives but they wouldn't have full control over everything. Nor would SEELE, nor would the UN. So you have to account for the human end of the politics.
On the alien side, the races gathered in this Ark might not be fully allied together. They'll have shifting allegiances, their own agendas, especially depending on how they ended up there. Here are some possibilities:
-One or more races of Lillim want to settle on Earth itself, since they are tired of living in space and want a new home after theirs was destroyed. The fact they can breed with humans who were born after Second Impact may be appealing to them, especially if they have a low breeding population to begin with. How they relate to humans could be interesting, especially if NERV is asked to facilitate them colonizing our planet.
-Most of the races would want to use the Evangelions to retake their homeworlds or save their planets before they fall to Angels, but which one to start with is a matter of contention. Do you go to the world with the greatest resources and most advanced technology that would be a major asset to Earth and the rest of the Lillim Alliance? Or do you go to the nearest world, regardless of how important strategically it is, and save it first? And how do the aliens and humans decide which one to go for first?
-Some of the aliens might have different feelings about the use of Evas, from believing it to be an abomination to some perhaps thinking humanity are the closest things to Gods by taming these monsters. Naturally this is going to vary from individual to individual, but remember they ARE aliens so there are going to be different viewpoints on this.
And of course... Cultural faux pas aplenty, given these are several different cultures all interacting for the first time.
- - - - -
The meeting room in NERV was spartan, but filled with comfortable furniture. And Shinji had been told to stay here... With his new adviser. An ambassador from the ship.
Shinji frowned thoughtfully as he looked at the... Well, alien next to him. The Lillim rep, who had been sent down as his adviser for all things alien, was actually very pretty. She was named Mu, and she had deep black hair that hung from under a strange organic like cap on her head, white and yellow skin, pointed ears, red eyes, and what looked like yellow wings that would retract and extend depending on her mood. Her clothing consisted of a tanktop and panties, somewhat bulky as they distributed water to her skin. As for the wings, they didn't let her fly, she explained, only swim.
"Mu Lillim... Are am... Am..." She frowned, licking her lips as she tried to recall the precise word.
"Amphibious?" Shinji asked. Mu nodded.
"Yes! Live water, on land. Our world very beautiful. Ships and people. Cities on and above water. Had rockets, too." She grinned. "Mu watched one when little. Launch... Rotating...?" She struggled. "Bounce... Signal...?"
"Satellite?" Shinji again guessed. Mu nodded again.
"Yes! Satellite... Then Old Ones come." She frowned. "Mu's Lillim fight back. Lose..." She pointed up at the sky, where the Ark was orbiting far above. "Send stars for help. Home ship come. Take away. Then take here."
"Wow," Shinji breathed. "How long have you been on the ship?"
Mu frowned again, concentrating on forming the words as she did the calculations. "One circle... Around your star... Is... One and some circle around... My star, so... Was eight circles around your star when leave... Seven circles around your star. On ship," she finally decided.
Shinji shook his head, hardly able to imagine it. "Seven years in space... Wow. I can't imagine it. You... You must have been really brave."
"Brave?" Mu asked, her cheeks turning red as did her wings. "Mu not brave... Shinji fight Old Ones. Very brave." She extended her wings around him, and leaned in close. Shinji blushed as well, and Mu grinned, showing off pointy teeth.
"Uh... Th-Thanks," he said. "Um... So..."
As uncomfortable as he felt, he did recall that Misato told him to "be diplomatic! Be understanding! They're aliens, after all! Be patient! And don't slouch, it's unattractive!"
"So, how old Shinji?" Mu asked.
"Uh... F-Fifteen... Circles around my star," He explained. Mu smiled.
"Shinji... Have... Girlfriend?" She asked.
"Ahhh... N-No."
"Want one?"
"... Sure?"
"Okay!" Mu said cheerfully, pouncing on him.
"ACK! H-Hey, hang on, hang on!"
In his office, Gendo watched over the feed from the window with a deadpan expression as his son ran from the amorous alien girl. He sighed and leaned back in his chair. Fuyutsuki, ever at his side, allowed a small smile to form.
"Perhaps you should have shown him Star Trek after all, Gendo."
"Perhaps I should have, Sensei..."
- - - - - -