I've beat Brendan on Route 119, but I didn't receive Fly. Also, at Rustboro City, I didn't receive Cut. Please Help! Thanks :)
Cut - house to the left of the Pokemon Center in Rustboro (that one with the trees). A man inside will give you cut.
Fly - you should have received it. Are you sure that was Route 119? Try going back after you get cut.