Can you Permanently delete a contact? When I try, if I type the person's name it still comes out and the phone number is "other" I have an 4S
You can delete the contact, but it still may be "searchable" with a spotlight search as it will remain for a time in the cache. If you don't want this, you'll need to restore your phone as a new device and avoid setting up from backup.
If I did that, I would lose all of my other contacts correct?
You would not lose any contact data if you are doing as the phone is designed and synching your contacts with a cloud service or an app on your computer.
Retrieving data ...