I had a repository with this history:

A---B---C---D

Then, this repository was "split" (basically, another repository was created with it's history beginning at 'D' with the use of git-subtrees).

Now, I have this other repo with this history:

# The same D as the other
D---E---F---G

How can I join these two "parts" of the same project storyline into one repository?
The final result must be:

A---B---C---D---E---F---G

I've already tried a number of things but all of them includes merging, and that's not what I intend, because merging doesn't preserve some changes like deleted files.
Also, I tried to generate patches for all changes of this last version of the repository and apply them in the old one, but got lots of error: <file> already exists in index errors.

Update

I found this other question about re-parenting a commit and that was exactly what solved my problem, a combination of both git replace --graft and git filter-branch.

Update 2

Now my task is complete and I posted the complete, correct answer to the problem below.

Update - The actual perfect approach:

Preparation

# Inside the older repo
$ cd old_repo

# Add the remote to newer repo with updated content
$ git remote add <remote name> <new_repo>

# Fetch the remote
$ git fetch <remote name>

# Track all branches of the remote so you have all of it's history in your older git (be aware of the remote's name in the command)
$ for b in `git branch -r | grep -v -- '->'`; do git branch --track ${b##<remote name>/} $b; done

# Delete the remote so you avoid messing up with the newer repo
$ git remote remove <remote name>

Now, I strongly suggest that you use a visual tool with this repo (like Gitkraken) since now it's kind of a mess there. You'll have two histories unattached to each other with, possibly, lots of duplicate commits.

Now, choose the commits that will be manipulated. Let's call commit with hash A the one in the older history, which will now be a parent of the commit B of the newest history. Now, you can use the script below (or run the commands manually) in order to join the trees and clean the mess left behind (trim the newer history right at the commit B, discarding all parents, since now it has a new parent).
(You must have git-replace and git-filter-repo installed)

#!/bin/sh

# Argument "$1" is commit A, and argument "$2" is commit B of the explanation above

if [ -z "$1" ] || [ -z "$2" ]
then
        echo "You must provide two commit hashes for this script";
        exit 1;
fi

git replace --graft $1 $2
result="$?"

[ "$result" = "0" ] && git filter-repo --force

Older, not important (that only serves to learn what to NOT do), answer below.

First I tried the approach with git-rebase, that didn't work out for a number of reasons, the biggest one is that it was a bit overkill for something like just changing the parent of a commit to another one, even if it's unrelated to the history.
Then I tried git cherry-pick to reapply all the history from point E..G to the old repository, also didn't work for a number of reasons but the main one was that it didn't copied other branches recursively.

Tried approach

$ git replace --graft <commit> <new parent to this commit>
Now, put the HEAD on the tip of the new history (the most recent commit in the main line you want to preserve), then:
$ git filter-branch <new parent to this commit>..HEAD

You may loose branches that are not yet merged onto the branch in which the HEAD is, and I couldn't find a way around that for now.