The problem is that Cthulhu is pretty much the ultimate entity of insanity and destruction, driving those that see him crazy and devouring the souls of those around him. He is immortal, we're pretty much equal to ants compared to him. The only wounds he's ever had was when someone rammed a steamship into his head, and he instantly began to recover (see the Call of Cthulhu).
He's not a Hollywood monster, I wouldn't want anyone to make him out like that in a film, he's an intelligent, godlike being who simply wants to crush the pests that are infesting his planet. I don't think you could do it like the Host. I hate to say it, but I'd rather see it more like Cloverfield. Not the terrible acting or camera control, but the very slow reveal of the monster, a leg here, a tentacle there, and instead show what his effects on people are. I can just picture him attacking a city, and the characters' seeing the results...waves of destruction, events that could only be explained as 'magical', people running through the streets, or weeping on the ground, driven mad by the simple appearance of Cthulhu's terror. Maybe even include his psychic powers, having him whisper into the minds of the characters, etc. You could make a fantastic movie about Cthulhu...without even seeing him!
The only problem is that an ending would be hard...it has to be depressing and nhilistic like Lovecraft's endings, and once Cthulhu's released it's impossible to stop him with our technology...