Debian - Stopping MySQL from booting at start

You want update-rc.d mysql disable. You don't want remove, As noted in the update-rc.d manpage:

A common system administration error is to delete the links with the thought that this will "disable" the service, i.e., that this will pre‐ vent the service from being started. However, if all links have been deleted then the next time the package is upgraded, the package's postinst script will run update-rc.d again and this will reinstall links at their factory default locations

Since Debian 8 (Jessy) using systemd by default, so try this:

systemctl list-units | grep mysql    # check for mysql unit name
systemctl disable mysql.service      # or whatever you find at prev step