Meh, unfortunately, you can only get your choice of 1 of either the DeepSeaTooth or DeepSeaScale on every Ruby/Sapphire/Emerald game. There is no other way to get one, outside of using a cheating device. You will not find these items attached to any other wild Pokémon, and they do not appear in the other games, like FireRed/LeafGreen/Colosseum. So, there really isn't a whole lot you can do, if yopu want a Huntail and Gorebyss for every one of your games, you will have to use a cheating device, or just keep on restarting a Ruby/Sapphire/Emerald game until you get to the point where you can get those items, then evolve your Clamperl, and trade it to another version, until you have enough Huntail and Gorebyss for every version.