Securing a multi-tenant, multi-database REST API

You should look at oauth 2.0 (RFC 6749) it has a number of flows which could meet your requirements.

Firstly you need to know if the clients are public or confidential. Issuing client api keys as you are doing is pointless if the clients are web browsers or apps downloaded to mobile devices as the secret can't be maintained. If they are servers then api keys are good. So that is your first consideration. Section 2.1 of the rfc deals with client types and that will determine which flows are applicable.

You need to separate identification of the client service from the user the client is acting for. Your backend database should have association of users with tenants and possibly api keys with users or user+tenant if you want to scope to just a single tenancy. I've implemented services where users can participate in multiple tenants so that may or may not apply to your case. I have successfully used the resource owner password credentials grant request so that a user can provide their username and password from a web browser. It sounds like you have used an out of band method to authorize the client so user credentials are not required. But if the client is a web browser or mobile app you can't rely on client auth and must get authorization from the user and that means providing user credentials.

Regardless of the flow you use you end up with a response as follows:

HTTP/1.1 200 OK
Content-Type: application/json;charset=UTF-8
Cache-Control: no-store
Pragma: no-cache

{
    "access_token":"2YotnFZFEjr1zCsicMWpAA",
    "token_type":"example",
    "expires_in":3600,
    "refresh_token":"tGzv3JOkF0XG5Qx2TlKWIA",
    "example_parameter":"example_value"
} 

The returned access token is what the client uses in its requests so that it can prove to the server its requests are authorized.

You have two options for the Authorization header, 'bearer' or 'mac'.

Authorization: Bearer xxxxxx

If your clients are using TLS then bearer tokens are the simple way forward. See section 7.1 of the RFC for more details.

Finally since access tokens are only temporary your clients can use the refresh token to request a new access token once the access token nears or exceeds its expiry. Its up to you if you want to use refresh tokens or not. Clients will need to store them securely at least the same level of protection they use for their api keys. In your system refresh tokens may be unnecessary for server-server interactions if the access lifetime is sufficient and user authentication is not required. If user authentication is required then refresh tokens may be useful if the client storage provides a sufficient level of protection.