What if an HMAC is correctly generated and sent with the data to the server, so far I know the server needs to know the original data with which the MAC was created in order to re-create the MAC and compare, but in this scenario the server has everything except that the key is hashed and not stored "plain". How can the server validate the MAC?
The significant difference between a (H)MAC and a hash is the key component. The idea of a MAC is, that it should only be possible to generate a specific MAC for a specific input by knowing a specific key. So if someone can generate a specific (given) MAC output for a given message input, he proves having the same key that was used to generate the given MAC output.
In other words: If someone calculates the MAC
x of the message
m by using the key
k (but only publishes
m), everybody who can generate
x proves to have knowledge about the key
To answer your question: If you need to generate the MAC without having the key on your server, you probably want to use a hash instead of a MAC.
If you don't know the key, you can't generate the HMAC. That's the whole point of a HMAC - it's a quick way to provide message integrity using existing key material. If you could regenerate the HMAC without the key, an attacker could simply generate a HMAC for a different message and alter the payload.
If you want a kind-of MAC which is such that it can be verified by using a "transformed key" which is itself not sufficient to compute other MAC values, then you do not want a MAC. What you want is a digital signature algorithm. One way to describe a digital signature algorithm is the following: it is like a MAC where the key for generating new MAC values, and the key for verifying a MAC value with regards to some data, are distinct. The two keys are mathematically linked with each other (the verification key works for MAC values which were generating with the corresponding generation key, and none other), but it is not feasible to recompute the generation key from the verification key. The verification key can thus be made public, while the generation key is kept private.
The most widely used signature algorithm is RSA (RSA is actually two algorithms, one for encryption and one for signatures; I am talking about the one for signatures; both algorithms share the same core mathematical operation, but are still quite different in their usage details).
HMAC is not a digital signature algorithm (despite what sloppy terminologists occasionally pretend).