Adain, this is a full roman name:

Quintus Octavius Lucii filius Cai nepos Lucii pronepos Sergia Sagitta

Quintus Octavius, son of Lucius, grandson of Caius, great-grandson of Lucius, from Sergia tribe, nickname Sagitta

Generally each roman familia (better call gentes only those of patrician blood) used only a series of names from their ancestors. Any name you like is good, since you can say the father of your Maximus could be a Lucius or a Publius or whatever you prefer.
Eventually 57 AD is a little in advance to use a nickname (Maximus) as praenomen, the habit to do it arrived a pair of centuries later, but it is acceptable.

You can find some useful information about Britannia in your time frame in Tacitus, De Vita Iulii Agricolae Liber. Agricola just was consular there.

The correct title for the governor of a provincia is Propraetor (named after served as Praetor in Roma) or Proconsul (named after served as Consul).