You can bundle arbitrary binaries with the --add-binary option on the command line or the binaries argument to the Analysis call in your .spec file. Check out the manual for details, but one example:
pyinstaller -F main.py --add-binary=`which redis-server`:bin
I don't know of a way to run arbitrary executables, but you could have some python code in your app to detect when you're bundled, find the redis binary, and start it up. Again, you can check out the documentation for details on how to go about this but, again, a example of how this could look (optional contextmanager elegance stolen from another answer):
import sys
import os
import subprocess
from contextlib import contextmanager
@contextmanager
def bundledredis():
    proc = subprocess.Popen(
        [os.path.join(sys._MEIPASS, 'bin', 'redis-server')])
    yield
    proc.terminate()
@contextmanager
def optional(condition, context_manager):
    if condition:
        with context_manager:
            yield
    else:
        yield
def realmain():
    print('doing stuff')
def main():
    with optional(getattr(sys, 'frozen', False), bundledredis()):
        realmain()
if __name__ == '__main__':
    main()