Inserting filename, reading data, inserting regex, and testing if each line matches - version 2
Pure functions

All of your functions both "do work" and print. You should separate logic and In/Out.

print('') is poor practice

If you want an extra newline just concat it to the previous message:

print('Empty regex\n')
return


Avoid noise

Maybe in a file of 1000 lines, my regex will match 5 lines, why must I watch 995 useless lines of output? Just output lines where it does match.

Prefer a dictionary or indexes to an array to a long if elif chain

if option == 1:
    filename = change_filename(filename)
elif option == 2:
    readData = read_file(filename)
elif option == 3:
    regex = change_regex(regex)
elif option == 4:
    test_data(readData, regex)
elif option == 5:
    break
else:
    print('Invalid input')
    print('Please enter a valid option')
    print('')


In all sincerity I don't know how to do this in this particular case, but iit would also give the  benefit of generating the printing message on the fly, instead of repeating the same thing twice.

Command-line?

But maybe all of that effort for the menu is counterproductive and you should allow the user to call the programme like:

python regex_script.py &lt;regex&gt; &lt;filename&gt;


by using sys.argv or argparse.

My take

This is my implementation of this program, it separates Input/Output and logic and can be used concisely from the command line:

import re
import sys

def lines_matched(regex, text):
    for line in text.splitlines():
        if re.search(regex, line):
            yield line

def main():
    if len(sys.argv) != 3:
        print("Usage: python {} &lt;regex&gt; &lt;filename&gt;".format(__file__))
        return 1
    regex, filename = sys.argv[1], sys.argv[2]
    with open(filename) as f:
        print('\n'.join(lines_matched(regex, f.read())))

if __name__ == "__main__":
    main()


argparse would make it more user friendly.