The whole point of git is to preserve history. So removing stuff from history is obviously not super easy.

"Without external tool" Why? Git defines a data structure on disk and not a monopoly on imolementation. The right tool for this job would be BFG.