To detect tampering, you first have to define tampering. You are receiving a message; what would make it a "tampered" message and not the "genuine" message ?
The usual definition of tampered/genuine uses the message source: at one point in space-time, the message was assembled or verified by an entity S, who declares it correct. This is the definition of the genuine message: the sequence of bits corresponding to that operation (or inspection) from S. At another point in space-time (later, and possibly elsewhere), the verifier V wants to make sure that the message is still genuine, i.e. the very same sequence of bits that S saw.
Knowledge is power: everybody can buy the same computers, so if the source S can do something that an attacker A cannot do, then this must be because S knows some specific piece of data (cryptographers call that a "key") that A does not know. Otherwise, if A knows everything that S knows, then A can make messages of his own which are indistinguishable from genuine messages.
If that secret value (let's call it K) is known to both S and V, then a MAC can be used. Such a setup works only as long as V is not an attacker either. If K is known to S only, then it must still be amenable to reliable verification from V, and we enter the realm of asymmetric cryptography, with digital signatures.
In both cases, we need some help from the context. Shared secrets don't materialize out of thin air; neither do certificates. We can have roughly the following situations and solutions:
S and V have met previously, or there is a secure channel to both from a trusted generator of random bits that only S and V can reach. Just use a MAC.
S and V share a secret, but it is of low entropy (say, a password that a human can remember). Password-Authenticated Key Exchange protocols (e.g. SRP) can be used by S and V to expand that shared secret into a better shared K which resists dictionary attacks. This implies that S and V can, at one time, talk to each other and run the PAKE protocol (this does not need a secure line; it can be done over the Internet; but it still must happen at one point). Once they have a shared K, they use a MAC.
S generates a public/private key pair, and V has a way to make sure that what he sees as "public key of S" has not been tampered with. This allows V to verify any signature computed by S. This does not solves your problem, but moves it: detection of tampering on the "message" has been moved to detection of tampering on the public key. However, this can help, because the public/private key pair may have been generated and verified in advance, long before the message first came into existence; and such a key pair can be used to protect several (many) messages.
V knows the public key of a trusted third party T, which uses its private key to sign the public key of S. This is an extension of the previous case, and is basically what PKI is about.
The important point in all of this is that no cryptography or other system will create trust. Cryptography just moves trust around. You still have to start somewhere, and that "somewhere" is the definition of what constitutes a "genuine message".