The ship will not set sail if the player challenges a Trainer after obtaining the move Cut, and loses the battle. The player would be teleported to the last Pokémon Center visited, and the ship would not leave the dock, making it accessible later in the game when the player had obtained Strength and Surf. Alternatively, only in the Generation I games, the player can take advantage of a glitch which causes the ship to reappear after it has left.
Impossible. If you didn't get Cut, the ship not have left. Something is wrong with your game or you didn't look carefully.
And you need Cut to get Fly.