Disabling iTunes Match, and having it stay disabled, on an iPhone can be tricky. iTunes Match is not compatible with an iPhone 3Gs so that shouldn't be an issue but it does work with the iPhone 4S. Here is the procedure I follow whenever I can't get iTunes Match to stay disabled on my iPhone 5:
1. Select Settings
2. Select General
3. Select Usage
4. Select Music
5. Select Edit
6. Push the red circle icon that comes up next to All Music.
7. Push the back arrows until you are in the main Settings area.
8. Scroll down to Music.
9. Disable iTunes Match again.
10. Push the Home button.
11. Turn your iPhone completely off.
12. Turn your iPhone completely back on.
13. Open up Settings again.
14. Scroll down to Music and select it.
15. Ensure that iTunes Match is still disabled.
16. Plug the iPhone into your computer and sync it.
I recently had to restore my iPhone 5 and start from scratch with it. iTunes Match would not turn off no matter what I did until I found this weird procedure online. It seems to work as everyone in the thread, including myself, has reported success.