Skyberries and Voidmelons or Voidberries and Skymelons

I don't know if you can use Android without logging into gmail, but I assume you can.

If you do, it simply backs up your contacts automatically into your gmail contacts. It's not a phone app of any sort as such.

There are Android phones that do a separate phone sync as well, of course, that would do it via an app.

I like it because I can log into my gmail anywhere I have internet and all my contacts are there, it's awesome!