A really creative, out of the box, idea would be to fashion your Titanic out of pykrete--a combination of sawdust and ice. There was actually a top-secret project in World War II to build air craft carriers out of these, because ice floats--the ships would be unsinkable! The frozen ice and sawdust material is also incredibly tough and durable.
The Mythbustersshow recently featured this idea, and took it one step further by using frozen newspapers.
If the Titanic had been made out of pykrete, it would undoubtedly have remained afloat, because of the composition of the building materials.