При первом коммите вы добавили коммит с data/ в свой репозиторий. Делая git rm -r data/ и затем git commit, вы сделали второй коммит, который удаляет data/. git push должен загрузить оба коммита, так что это не помогло.
Кроме того, git rm --cached удаляет только данные из индекса. Я не думаю, что ваш второй коммит фактически удалил какие-либо файлы, но вы можете проверить это с помощью git log --stat.
Вам нужно переписать историю с помощью интерактивного перебазирования. Это не столько переписывание истории, сколько переписывание новой истории. Как страховой полис, начните с размещения тега, где master с git tag before_rebase. Тогда, если что-то пойдет не так, вы всегда можете вернуться к before_rebase и повторить попытку.
Вы говорите git, что хотите переписать историю, возвращаясь к origin/master с git rebase -i origin/master. Тогда вы получите редактор с чем-то вроде этого:
pick 064f41f Some change
pick 1ca69c3 Some other change
pick 1fa8921 Remove data/
pick 984alkj Huge amounts of data/
pick 82adlkj Bug fix
Просто удалите строки, представляющие нарушающие коммиты, сохраните и выйдите из редактора. Затем Git повторно применяет каждое оставшееся изменение поверх друг друга. Вы можете получить конфликты, разрешить их, как любое другое слияние.
Как только вы закончите, используйте git log, чтобы убедиться, что изменения действительно пропали.
Теперь вы можете нажимать, и data/ полностью ушел из истории.