While waiting for native Matrix clients to mature, I found that the Android version of FluffyChat works quite well, even on my phone which is still limited to the old Alien Dalvik version (I think it corresponds to Android 4.4). E2EE works (although some older messages weren’t possible to decrypt) and notifications work (blue indicator light and icons that appear to the left but no vibrations), so finally I have usable Matrix client! A native client is still desirable, but this is much better than nothing.
Edit: The notifications I saw came from Konheko, so I’m not sure that FluffyChat notifications work.