In this case I would read puto more as a side remark to the clause deus fio.
You could emphasize this with punctuation:
Puto: deus fio.
I think: I'm becoming a god.
The verb puto is indeed grammatically detached from the rest of the clause.
It is grammatically correct, but it is not really grammatically connected to deus fio.
(The semantic connection is strong, of course.)
It would also be grammatical to say puto me deum fieri, but that would give a somewhat different tone.
The word credo is often used in a similar fashion, essentially as an interjection.
For example, consider this quote from Cicero, Pro S. Roscio Amerino 76.7–8:
Litteras, credo, misit alicui sicario qui Romae noverat neminem.
He sent letters, I think, to an assassin who knew no one in Rome.
Compare this to "I think that he sent letters..." to see the difference between puto as an "interjection" and with an ACI.
I don't know if this became more common in later Latin, but the construction does exist in classical authors like Cicero and it seems very common in Plautus.