REST API security

I'm working on a REST API that will let an Android app communicate with a website. Sadly more than half of the people that are going to use it can't do so over HTTPs, so I will have to maximize security over HTTP.

What needs to happen is simply authenticating through a REST API, username/email and password.

I've thought about either hashing the password (or username+password) clientside and sending that to the server, but then you'd end up with simply a second password anyone could still auth with. Hashing the password clientside would even mean that if someone gets access to the database that person would be able to access all accounts.

What is a way to safely authenticate over HTTP? I have full control over both client and server so there's not really anything that's not possible.