Four fours to get any number
I am looking for code-style advice and maybe a better algorithm suggestion.


As for coding style, first and foremost, please follow PEP8.

Simplify

You could simplify get_starts using product from itertools:

def get_starts(n):
    sqrt, power, fact, gamma = int(n ** 0.5), n ** 2, math.factorial(n), math.factorial(n - 1)
    return product((sqrt, n, power, fact, gamma), repeat=4)


I also dropped the unused lst parameter.
In fact many of the functions have unused parameters,
remove them everywhere.

Use generators, they are awesome

Since you accumulate solutions in an array,
the program seems to freeze for a few seconds while calculating,
rather than printing the solutions that are ready.
You could improve that by using a generator instead, for example:

def solve_44(max_):
    for i in range(max_):
        yield how_to_obtain(i, [concat, op.add, op.mul, op.sub, div, op.pow, op.mod])


def main(max_):
    none_count = 0
    for solution in solve_44(max_):
        print(solution)
        if solution is None:
            none_count += 1
    print("The random search failed to find a solution {}% of the times.".format(
        none_count / max_ * 100))


Another correction here is using is None instead of == None for comparing with None values.