I think the key to rewriting Prometheus would start with Charlize Theron's Meredith Vickers. Her character has the most interesting backstory and seems like she's best suited to have a legit arc/journey but she ends up being used as nothing but a rather weak foil for the movie's hero, Elizabeth Shaw.
What we know of Vickers is that she has issues with her father, wanting him to just die so she won't be just an empty suit at the head of the boardroom table. But those feelings probably stem from the fact that she was never good enough for him; he wanted a son so badly that he actually went out and built himself one (which could have been turned into a great sci-fi sibling rivalry but was basically little more than those two not liking one another and Vickers deciding to prove her humanity by sleeping with a man... which is kind of problematic on the feminist front.) She's also a non-believer and could be given the arc that she eventually sees the light and understands that there's so much more going on in the world than what she understands/has focused on.
There's so much to mine there but nothing really comes from it and, instead, we're supposed to focus on Shaw, who has a backstory that doesn't seem to actually matter. As Alyssa Rosenberg over at Think Progress pointed out, the issues of her wanting to be a mother really play no role since as soon as she finds out she's pregnant, she immediately (and understandably) wants the fetus out of her. If you cut out every mention of Shaw's backstory, nothing in the movie changes. That's a problem. (An even bigger problem is that, after discovering the hieroglyph at the start of the film, Shaw doesn't actually do anything. At no point in the film is her expertise needed. She's an almost completely passive "hero". She barely even registers as a threat to the antagonists. After she's impregnated with the alien, she runs off and apparently nobody chases her to stop her from cutting it out and when she reappears in Weyland's room, people barely bat an eyelash and nobody, not even David, wonders, "Hey, what about that alien being that you used to have in your belly? Should we check on it?" And Shaw doesn't seem to make a big deal of it either. I'm sorry but it's bizarre when the biggest moment of the movie to that point is treated like an afterthought.)
And in terms of her arc, Shaw has more of a 360 as she thinks we were invited to the faraway moon, then thinks we never should have come, but finally thinks they have to go FURTHER to find out the truth. I'm not sure why she makes that last leap because, if the Engineers are as quick to destroy people as the one they discovered in the pod, she's not going to talk to them for very long before they crush her and she will probably just serve as a reminder to the Engineers that they sent some of their cronies to a moon a few thousand years ago to make weapons and they haven't heard back from them. She'll probably just remind them to finish the job they've inexplicably left undone.

So, in fixing up the script's story and characters, the first thing I'd do is decide the fate of Vickers. Either she should become the hero or her character should be dissolved and all of the interesting backstory elements, including her being Weyland's daughter, should be given to Shaw. It's far more interesting to have Shaw be drawn to the history of man because of her father's love for an android son than it is a random flashback of her and her father in the jungle (and then an equally jarring moment of David bringing up that the dad died of ebola.) I mean, if those elements are at all important (and they seem to just be there to build the cross into the movie), just give them to the mother, who is completely absent in the film.
The bottom line is that by eliminating Vickers and giving Shaw her connection to Weyland, we could improve the hero's journey, give some depth to our hero (who, as the film is currently structured, we basically only root for because she's the only main character who isn't a jackass), and improve the driving force for all of our characters.
And that's the second key issue with Prometheus

Make the Others Matter
Once we fix the hero problem, the rest of the characters need to be addressed. Right now, they mostly exist just to fill their role. Janek is there to crash the ship. Charlie is there to get poisoned. None of the side characters have a journey or an arc of their own.
But if we do decide to give Vickers's backstory and connection to Weyland to Shaw, then her character can be deleted and all of her other key moments (of which there are really only two) can be given to Idris Elba's Captain Janek. This would start the necessary re-write of that character as someone who was about: protecting himself and his ship first, following his employer's orders second, and caring about everyone else never. Janek, as more of a hard nosed, save myself type of leader, would have shown his allegiance via his flamethrowing Charlie and not wanting to open the hatch. I would also add a story of him going into private mercenary work instead of military because he abandoned some troops or something (Fashion a moment much like the scene in Jaws when we learn that captain's backstory and motivation.) This would have made his arc better and boosted the moment when he decides to sacrifice himself and take the alien ship down.
As it is now, Janek's just kind of a loosey-goosey asshole who likes fucking with people... but then states he's not SO into fucking with people that he wants to bring the alien shit back to Earth and wipe out the population so it's not a huge decision for him when kamikazees into the alien ship. (Also, we might have to add a note that Janek lives on a terraformed planet and not Earth so he'd have somewhere to run and the threat to Earth wasn't necessarily a threat to him and his family's home.)

While I think the Captain's issues can be fixed by adding him as the antagonist in a couple of scenes and maybe adding one or two more scenes focusing on him, the issues with Milburn and Fifield are laughably huge. Literally nothing about these guys seems to make sense. The tattooed geologist Milburn is in charge of the mapping and he gets lost. Milburn's dialogue consists almost completely of his saying that he doesn't want to be friends and wants to be left alone but he inexplicably stands around and waits while his non-friend plays with an alien snake. Which, of course, is the biggest problem with that scene - after seeing a hologram of the huge Engineers running for their lives and then finding actual Engineers piled up, dead, a frightened Fifield and Milburn decide to run... only to later bump into a living being, the only living being that they know of and what you'd assume probably killed all the Engineers, and cowardly Fifield suddenly thinks he can snakecharm it into being friendly. And, again, Milburn decides to stay around to watch when we've already see him flee for the mere hint of a threat, nevermind an actual alien being. Nothing these guys did made sense and either their characters need to be reengineered to fit their demise or their run-in with the snake should be rewritten. Personally, I'd make it that they were victims of David's experimenting so we can bring in the element that the crew is actually just guinea pigs for David as he tries to find Weyland's, which leads to the next problem...

Make Revelations Matter
"Prometheus" included two of the weakest revelations I've seen in a very long time. The first, that Weyland was actually on board, was hinted at strongly and then came about and... well... there he was. It kind of exposed an ulterior motive like Reiser's character in Aliens although the pregnancy scene in which nobody follows Shaw or tries to stop her from aborting the monster fetus ups the gross factor to make up for the lack of tension it had when compared to Reiser locking Ripley and Newt in the room with the facesucker in Aliens. I know it's very Lindleof to make these moments somewhat vague, which is fine, but if you're going to do that, you might as well eliminate the revelation and let it be known that Weyland is on board from the beginning because there are few things less cinematic than a vague revelation.
The second weak revelation was that Vickers was Weyland's daughter. It was pretty pointless and adds nothing to the film. However, if we dump Vickers and play Shaw as daughter, the revelation and Weyland's being on the ship are given some heft. Charlie can feel duped that his lover was lying to him. The other scientists can start to question why they were brought out here - for a great discovery or just to save the father. Shaw's motives can be questioned. David's poisoning of Charlie can be more devious and serve another purpose for him as he's also going to potentially kill his "sister". Having Shaw be Weyland's daughter would heighten every element of the film and make the father-daughter connection an actual plot point as opposed to a fairly random character moment.

And finally....

What's the Question? In his discussion on i09.com, Lindleof mentioned:

"The movie asks the question, were we created by these beings? And it answers that question very definitively. But in the wake of that answer there's a new question, which is, they created us but now they want to destroy us, why did they change their minds? That's the question that Shaw is asking at the end of this movie, the one that she wants answered."

My problem with this thinking is that that question was pretty much answered in the very first scene. After that, it was basically two hours of getting the characters to catch up to where we were so they could... ask another question.
I would have eliminated that first scene and let the audience discover the truth along with the characters. Nothing was really gained from us knowing more than the scientists, and giving us that revelation might have made the revelation that the Engineers were on this moon to kill us even stronger. (Granted, that doesn't fix the problem of: if thousands of years ago, the Engineers wanted to kill us, why didn't they go down and kill us instead of teaching people how to draw sketches of the planet/moons, especially since it was pretty clear that we were nowhere near the technology to get to said moon.)
Also, if we are trying to discover where we came from along with the scientists, the realization that the only reason they are there is to save Weyland carries more heft. Not only have the crew been duped by Weyland, so have we. And again, I'd make it that there are more David experiments on other crew members and they slowly realize that they aren't a crew, they are guinea pigs in the search for immortality for Weyland.

Given these changes, I think Prometheus could have been a great movie. As it stands, it's just a bunch of questions about the meaning of life and where we came from based around the world from an old science-fiction franchise. In other words, it's basically a new form of Scientology and I'm just not going to find much interest in discussing or thinking about how some made up Engineers might have affected the meaning of my existence. If I was interested in that, I'd skip the movies and go to Church.

And the usual note: Comments aren't working so either e-mail me at admin@soulhonky.com or go to the SoulHonky.com Facebook page or Twitter if you've got something to say.