Would you be able to do this at the app level? Maybe I don't know about it enough but I'm thinking you would need to have direct access to the radio to encode the paging signal. Then wouldn't the base station have to understand our different tones so it can preserve them in order to pass them on?
Encode the positive integer (index of the preset message) in the length of the ringing:
1 second before cutting = OK
2 seconds before cutting = Be there in 5 minutes
3 seconds before cutting = No
4 seconds before cutting = ?
5 seconds before cutting = haha
... etc
It would be much easier to do between friends (understand they are sending a message, not phoning you) but a well coded application could disable its vibrate+ringtone on ALL incoming calls by say, 3 seconds and the message can be placed in that window (so the user doesn't accidentally pick it up thinking it's a call).
There are many ways to do it. A well thought out version can become immensely popular.
Oh right! I mistook your original post for a completely different scheme. Don't know why but I was thinking about encoding data in a single call by reencoding the paging signal.
Your idea is much more feasible and actually kinda cool.
cool idea tho