Du könntest so ein Problem auf jeden Fall mit einer MySQL-Datenbank lösen. Der Vorteil davon ist, dass man so einen Server kostengünstig und effizient betreiben kann. Im Prinzip brauchst du nur einen Webserver der php beherrscht und auf dem MySQL installiert ist. Das kannst du mit jedem beliebigen Rechner realisieren, auch mit einem Raspberry Pi, allerdings ist die Rechenleistung von dem sehr begrenzt. Wenn du das wirklich ordentlich realisieren möchtest, solltest du dir einen Hoster mit Dedicated Servern raussuchen.
Also Webserver könntest du einfach einen Apache-Server mit MySQL einrichten/mieten.
Prinzipiell kannst du das mit einem Restful Service realisieren. Dabei könnte die Android-App über http mit einer php-Datei kommunizieren, welche wiederum die Daten in die Datenbank einträgt oder ausgibt. Bei Ausgabe der Daten bietet sich JSON an, einfach zu implementieren.
Das ganze kam mir anfangs auch sehr komplex vor, hab mich dann einfach mal in Ruhe drangesetzt und ein paar tests gemacht.
Edit:
Das Speichern der Daten auf dem Android-Gerät kannst du dann über eine SQLite-Datenbank machen. Hier noch ein paar Links:
Android SQLite
Android REST