(solved, see bottom of the question body)
Looking for this for a long time now, what I have till now is:

• http://dound.com/2009/04/git-forever-remove-files-or-folders-from-history/ and
• http://progit.org/book/ch9-7.html

Pretty much the same method, but both of them leave objects in pack files... Stuck.
What I tried:

git filter-branch --index-filter 'git rm --cached --ignore-unmatch file_name'
rm -Rf .git/refs/original
rm -Rf .git/logs/
git gc

Still have files in the pack, and this is how I know it:

git verify-pack -v .git/objects/pack/pack-3f8c0...bb.idx | sort -k 3 -n | tail -3

And this:

git filter-branch --index-filter "git rm -rf --cached --ignore-unmatch file_name" HEAD
rm -rf .git/refs/original/ && git reflog expire --all &&  git gc --aggressive --prune

The same...

Tried git clone trick, it removed some of the files (~3000 of them) but the largest files are still there...

I have some large legacy files in the repository, ~200M, and I really don't want them there... And I don't want to reset the repository to 0 :(

SOLUTION: This is the shortest way to get rid of the files:

1. check .git/packed-refs - my problem was that I had there a refs/remotes/origin/master line for a remote repository, delete it, otherwise git won't remove those files
2. (optional) git verify-pack -v .git/objects/pack/#{pack-name}.idx | sort -k 3 -n | tail -5 - to check for the largest files
3. (optional) git rev-list --objects --all | grep a0d770a97ff0fac0be1d777b32cc67fe69eb9a98 - to check what files those are
4. git filter-branch --index-filter 'git rm --cached --ignore-unmatch file_names' - to remove the file from all revisions
5. rm -rf .git/refs/original/ - to remove git's backup
6. git reflog expire --all --expire='0 days' - to expire all the loose objects
7. (optional) git fsck --full --unreachable - to check if there are any loose objects
8. git repack -A -d - repacking the pack
9. git prune - to finally remove those objects