When I turn off both my mobile data and my wifi, I get a strange notification

I am not sure that you can get rid of it. It is just your phones way of alerting you that you have no possible data connection.

 

It looks like you have automatic synchronization enabled. The phone tries to connect to server and , surprisingly, fails. This can be caused by Google synchronization (altough Google could disable this in flight mode) or by other applications trying to syncronize data (Email, Facebok, ...). I have the automatic synchronization disabled and no warning appears when switching to flight mode.

 

Of course, with auto-sync off, you have to manually sync your contacts and calendar every now and then to make sure they are backed up.