I know this is an old thread but it shows up pretty high on Google and is the only relevant one to my own quest when I was trying to remove Gapps/Google Apps from my phone, so I figured I'd add my two cents.
The above answers did not work for me. What I did was the following:
(WARNING: this may brick some devices!)
- Forcibly flash a bogus image using a low level flash tool (e.g Androxyde FlashTool) into the phone's system ROM, e.g 10mb worth zeroes should do the trick to overwrite the file allocation table.
- Install recovery if it has been removed by the above operation. You can do this by holding the phone specific button combo to put it in flash mode (e.g power and volume-down), and then flashing the boot.img file that's included in most rom files using the flash tool you used in the previous step.
- Boot into recovery, and install your rom of choice.
This will create a completely clean system ROM with only the applications included in the ROM itself.
If you decide that you want Google apps later after all, just search for 'GApps android' or go to http://opengapps.org .