Male chocobos are random everywhere you would normally catch chocobos.

As for weapon, wait for him to stop moving before running into him.