I see a few options for persistent nodes (not just a player):
1) Use an auto-load singleton, which will make your node present in all scenes of your game (even the main menu though, if you have one). Documentation here: http://docs.godotengine.org/en/stable/learning/step_by_step/singletons_autoload.html
Next solutions require a bit of scripting:
2) Dynamically instance the player, remove it from the tree (remove_child) before changing scene (it won't delete it), and add it back in the scene once it is loaded (add_child). That requires a bit of code in a singleton (like in 1) )and the setup of "spawn points" using Position2D for example, so that you know where to put the node.
3) Don't use change_scene, because as you noticed it replace everything by a new scene. But because Godot games are scene trees, an alternative is to have one scene that removes and loads the others under a child node. This way, the "container" can have common nodes that will be preserved because they are in a parent or another branch. I use this approach in my own game to preserve UI and global effects because they are common to all levels and won't need to be reloaded everytime. One drawback is that scenes are less likely to be tested independently because they require to be in their "container" at runtime, but I worked around it somehow.