How does one provide a secure and authentic communication channel? Let assume two participants Alice and Bob who perform a given protocol which is a sequence of messages exchange between them.

My question is: How can I provide a secure and authentic communication channel using cryptography, so that when Bob sends a message "M" to Alice, the latter will be able to know whether or not the message "M" is from Bob?

Is there a solution without using certificates?
"Authentic" is defined with regards to an identity. A message from Bob is authentic only insofar as Bob is distinct from Charlie. There must be something which, from the outside, makes Bob and Charlie two different entities.

In a computerized world with networks, Alice can "see" other people only through the data they send. Moreover, everybody can buy a computer, so what Bob can compute, so can Charlie. The only remaining way for Bob to be distinct from Charlie is what Bob knows. That's how identities are defined in cryptography: you are what you know.

So Alice can make sure that a given message $M$ comes from Bob (and not Charlie) only if Bob does some computation over the message $M$ which involves some data that Bob knows, but not Charlie.

A basic, traditional setting is when the "secret" known by Bob is a sequence of bytes which Alice knows too. That sequence of bytes can then be used as key in a Message Authentication Code: this is a kind of checksum, which Bob can compute over $M$, and that Alice can recompute over $M$ since she also knows the "secret"; that's how Alice verifies the MAC. But Charlie cannot compute the MAC since he does not know the secret. The shared secret can also be used as key for symmetric encryption, so that the message contents can remain confidential: there again, Alice can decrypt the data encrypted by Bob (since she knows the secret) but Charlie cannot. Combining symmetric encryption and a MAC while using the same secret as key for both can be somewhat perilous; there are subtleties.

The traditional scheme has the drawback of having a shared secret between Alice and Bob: since identities are "what we know", this means that Alice and Bob are really the same entity, "Bobalice". The scheme above is about Bobalice talking to himself/herself. That's not a useless model: that's what happens when you encrypt some data so that you can store it, and decrypt it back later; i.e. you are talking with yourself through time. In practice, for two distinct human beings, this means that Alice can authenticate Bob's message, but cannot prove it, because whatever MAC Bob computes, Alice could have computed as well. Also, setting up a shared secret between two people can be hard in some contexts (they must have met beforehand, or something like that). Finally, in the context of software (which is, by definition, quite dumb), there can be some issues if an attacker tries to send back to Alice one of her own messages: Alice knows that a message $M$ is from Bob because only Alice and Bob know the secret value which is needed to compute the MAC, and (that's the critical point) Alice remembers that she did not send that specific message -- so it must be from Bob. The "remember" bit can be tricky; a simple way is to add the sender name in each message (so that a message from Alice always begins by "From Alice").

To go further, we need public key cryptography. This leads to the following protocol: Bob has a key pair for an asymmetric encryption algorithm (e.g. RSA) or a key exchange algorithm (e.g. Diffie-Hellman). The "public" part of the key is known by everybody (that's what "public" means), including Alice. The "private" part of the key is known by Bob only (it is "private"). Alice choose a random sequence of bytes $K$ and encrypts $K$ with Bob's public key; she sends the result to Bob. Bob uses his private key to decrypt $K$, at which point ALice and Bob have a shared secret ($K$) and they can use it as above, with symmetric encryption and a MAC.

With public key cryptography, Bob is distinct from everybody else, including Alice; he has his very own private key. Bob's identity is defined as "whoever controls the private key corresponding to that public key". This still requires Alice to be able to know, in a reliable way, Bob's public key, where "reliable" means that Alice will not be induced into mistakenly using Charlie's public key. That's where certificates come into play: a certificate is a piece of data which is signed by an authority and says: "this is Bob's public key". It is a way to distribute public keys (and their binding to identities) in a verifiable fashion. There can be other ways.

For instance, in the SSH protocol, a client (which tries to connect to a remote server) knows the server public key by remembering it (the client stores a local copy of the public key). This requires a specific bootstrap procedure, for the first time the client connects to a given server, but afterwards the server key is known to the client, and the client just uses it to authenticate the server.