I authorize all REST API requests by checking token in Authorization header:
POST /rest/resource HTTP/1.1
Host: domain.com
Authorization: Bearer AbCdEf123456
The token is plain text, using HTTPS. However, the token is salted and hashed in the database.
How could I authenticate the request?
There must be some elegant way since for example for google maps the "API key" (token) is sufficient.
Use JWT (JSON Web Token) as authorization bearer. JWT can have user id in the payload. You can also easily verify if JWT was issued by trusted party (probably you). The good thing is that you can verify JWT without reading values form database. It is completely stateless.
This is simple explanation how JWT works: http://www.intridea.com/blog/2013/11/7/json-web-token-the-useful-little-standard-you-haven-t-heard-about
You can find library for JWT for almost any language (just google it)