Choice of database: relational databases such as Mysql or Postgres are not necessarily harder to scale than MongoDB and such. In many cases it's quite the opposite. Here is a great comparison of different storage technologies: http://kkovacs.eu/cassandra-vs-mongodb-vs-couchdb-vs-redis
"Event-driven" architecture: You have a lot of requirements that boil down to "when this happens, do something". A typical way to build an architecture like that is to think of events being emitted and event listeners acting upon those events. For example: "message read" is an event that your Android app will be sending back to the server when somebody reads a message. Server can have a listener waiting for events like that, and every time it gets one, it'll go and mark the message as "read" in the database. You can think of many use cases like that: "message received" is an event - listener will take that message and forward it on to the recepient. Another example: "user connected" - when somebody launches the app and connects to the server, you'd probably like to forward any messages directed to them that gathered while they were offline - that can be easily addressed using events. You would typically have a message queue as the center piece of your application, with all kinds of listeners connected to it, and all events that are emitted sent through it.
3rd party solutions: If you are doing this as a learning exercise with focus on Android development, consider using a 3rd party solution that can take care of a lot of your backend needs. One example is https://www.firebase.com/. Building a full-blown backend system for an app like this, with serious scaling and performance requirements is a lot of effort which will take your time away from learning Android.
build it step by step: I'd start with a very simple back-end app without a database, and develop it in parallel with the Android app. Make sure you understand as much as possible about your requirements before you make big decisions about what database to use etc - the only real way to do that is to prototype and iterate as quickly as possible.