Is it possible for Alice and Bob to both sign a message "simultaneously"? Let's say that there is a message which is considered valid if signed by both Alice and Bob.

Alice could sign the message and then give it to Bob, so that he can sign it and give it back to her.

But, for various reasons, Alice doesn't want Bob to have a fully-signed message that she doesn't also have. If she just signs it and sends it, he could sign it and not send it back.

Is there some way that both of them can sign the message (maybe interactively?) so that it doesn't become valid for Bob if it isn't also valid for Alice?

(This could be done by a trusted third party who would simply escrow the message until it had received both signatures, and then release both signatures to Alice and Bob. Of course, I want a solution without a third party.)
This is one of the earliest questions that was asked in modern cryptography. There is a proof that you cannot achieve completely fair contract signing. However, there are some reasonable alternatives. There is one direction called "gradual release" which I personally do not like. A model that I think has a lot of promise is called the "optimistic model". In this model, there is a trusted third server that is only invoked in case one of the parties cheats and may obtain a signature without the other. This model is very nice in the sense that once the server exists, there is no motivation to cheat since anyway an adversary knows that it cannot gain anything. I note that the server is trusted to answer when a party asks for its "help", but does not learn anything. This model was introduced by Silvio Micali in Fair Electronic Exchange with Invisible Trusted Parties. You can read more about this model in Optimistic Fair Secure Computation by Cachin and Camenisch, and Analysis of a Fair Exchange Protocol by Shmatikov and Mitchell. 

Another direction which I really like is called Concurrent Signatures. In this model, one party gets the signature first. However, if the other party sees the signature then it can use that to complete its own signature. So, it's actually not fair (one has the signature first) but if the first ever wants to enforce anything with its signature then it would have to show it to the second, in which case the second can complete the signature it is supposed to receive. In most practical cases that I can think of this is sufficient, and it elegantly bypasses the impossibility results that exist. This model has the advantage that you don't need a (minimally) trusted third party (which is problematic in practice).

Finally, I'll point to the recent use of Bitcoin to ensure fairness. The paper How to Use Bitcoin to Design Fair Protocols shows how to do this (albeit theoretically). The idea here is very very nice.