How to remove GMail contacts from Messaging app on Samsung Galaxy S Advance?
In Android 4.1 Jelly bean follow the following steps: 


Open the Contacts app
Tap the Setting touch button
Select Contacts to display
Select Phone


A similar procedure should work also for the earlier Android 2.3 Gingerbread.