As all other answers said, your problem is really hard. But since you asked for a methodology, that questions is easier to answer.
First of all, the methodology you use depends a lot on the organization you are in. Some organizations simply follow waterfall development methodologies (i.e Military) and there is nothing you can do. On the other end there are organizations that only develop projects using agile methodologies. You must take this into account before taking any decision.
Second, agile methodologies are being used more and more these days because they produce better products (although there is no clear scientific evidence of this, most project that have moved to agile are very happy after the change). I would also recommend agile development (short iterations, working product, automatic tests, etc...). You can mix this with TDD to get more robustness, but it is not a must.
Last, but not least, even if you are doing agile, you still need to define your requirements in an exact way. Agile is NOT a synonym to not having defined requirements! it means that you implements the requirements step by step. With the complexity of what you are trying to achieve, you MUST define your requirements very well. If you don't have good requirements not event testing will help you (sorry for repeating myself, but I find this is a very important point).
And good luck.