While I can't find much on when the sword was adopted (at least for the moment) I have found several sources that point towards answers for some of your other questions here.
It appears that the method of death varied depending on who you were, or who was punishing you. The following refers to the reign of Caligula.
Many men of honourable rank were first disfigured with the marks of branding-irons and then condemned to the mines, to work at building roads, or to be thrown to the wild beasts; or else he shut them up in cages on all fours, like animals, or had them sawn asunder. Not all these punishments were for serious offences, but merely for criticising one of his shows, or for never having sworn by his Genius.
The Lives of the Twelve Caesars by C. Suetonius Tranquillus
Note: As far as I can tell, "Being sawn asunder" was a method of execution by saw, whereby the convicted would be sawn either horizontally or vertically in half.
For the most part, it seems that non-roman citizens would be executed by Crucifixion rather than by ax - a method of execution that was illegal for use on Roman Citizens (crucifixion) - but it is not impossible, or likely, that the use of the ax was stopped when executing non-romans.
However, I have yet (But I am not an expert on this, and have not done a huge amount of reading) to find any indication that Roman citizens were only executed by decapitation by sword and were never executed by crucifixion. For example, both sources I've cited above indicate that people were executed by being thrown to the beasts, although it is not clear about their citizenship or class, and one lists several other methods of execution used at the Colosseum.
The Roman Executions at the Colosseum included other forms such as:
Being burnt alive
Being bound by the feet to the tails of wild horses and dragged to death
Being torn to pieces by wild beasts
Beaten to death Burned with plates of red-hot iron