How to "append" Op at the beginning of a TensorFlow graph?

Finally found a way to do this. I am sure the function Yarolsav mentioned in the comments does something similar internally.

new_input = graph_def.node.add()
new_input.op = 'new_op_name'  # eg: 'Const', 'Placeholder', 'Add' etc
new_input.name = 'some_new_name'
# set any attributes you want for new_input here
old_input.input[0] = 'some_new_name'  #  must match with the name above

For details about how to set the attributes, see this file.