Delete cookies in Safari manually
Yes, there is a way to effectively remove all cookies from Safari via the terminal as well, preventing the auto-restore phenomenon you described. I wrote a simple shell script some time ago to achieve this. 

I tested this on macOS 10.12.3 and Safari 10.0.3 and it works. 

Warning: The tests I did weren't as thorough, meaning: some of the files deleted by this script might not actually be necessary in order to achieve the removal of the cookies, you should trial-and-error your way around it to narrow it down if you like. I personally use the script 'as is', but in your personal situation that might mean you'll lose some data that you actually wanted to keep. 

Copy this into a simple shell script and run it (be sure to also copy the 'killall' command):

rm -rf ~/Library/Safari/History*
rm -rf ~/Library/Safari/Auto*
rm -rf ~/Library/Safari/LocalStorage
rm -rf ~/Library/Safari/Downloads.*
rm -rf ~/Library/Safari/Databases
rm -rf ~/Library/Safari/SearchDescriptions.plist
rm -rf ~/Library/Safari/WebFeedSources.plist
rm -rf ~/Library/Safari/Last*
rm -rf ~/Library/Safari/Recently*
rm -rf ~/Library/WebKit/com.apple.Safari
rm -rf /Library/Cookies
rm -rf ~/Library/Cookies
rm -rf ~/Library/Caches
rm -rf /Library/Caches
rm -rf ~/Library/Application Support/Oracle/Java/Deployment/cache
rm -rf ~/Library/Preferences/Macromedia/*
rm -rf ~/Library/Containers/com.apple.Safari.*
rm -rf ~/Library/Application Support/com.apple.sharedfilelist/*
rm -rf ~/Library/Preferences/com.apple.coreservices.useractivityd.dynamicuseractivites
rm -rf ~/Library/Preferences/*SpotlightNetHelper*
rm -rf ~/.oracle_jre_usage
rm -rf ~/Library/Preferences/com.apple.sharekit.recents.plist
rm -rf ~/Library/Saved*

killall -KILL nsurlstoraged