The message deleted by us: app/file.php means precisely what you described, namely that someone deleted this file in the master branch on which you are rebasing new_branch.
Assuming that the delete has not yet been staged and you want to keep this file, then you should git add the file to mark it that it should be kept:
git add app/file.php
Then, resolve all other merge conflicts and do git rebase --continue
Note that if you wanted to accept the delete you would do git rm instead.