You can always introduce other forms of authentication later. I have a slight preference for basic/digest auth as the secret isn't part of the URL, and therefore not cached/logged by any network equipment.
edit: typo
Does basic auth works if the client is a browser and you want to have a nice login screen?
You can solve this with a token/user blacklist. There are desirable (and undesirable) characteristics of using a blacklist instead of a whitelist, but you don't lose this capability.
Do the simplest thing that will work.
This is a complex distributed systems topic, and there are applications for both.
"I can access this thing" are totally not that for the 99.9% case. Do the simplest thing that will work--and the simplest thing so very rarely involves public-key cryptography!
Appypolylogies.
I would consider more complicated solutions only if you first come to conclusion that these simple things are not fit for the purpose.
True that some fancy token based solution may reduce database load, but if the API is doing something useful then that one primary key lookup and potentially the password hashing won't be a show stopper. Drawback with tokens and skipping the DB check is that you can't simply kill a client behaving badly. With API key you can just change the key and requests stop immediately (with MVP product this might be an issue, since maybe you have decided to add rate limits etc later).