Simple elementary cellular automata with high period?
Used symbols will be $0, 1$, table $T$ with $18$ elements ($L=18$), and one element for register $B$.
Initialize table with any configuration with at least one element set to $1$.

At generation step do:
B = T[0] Xor T[7]
T[i] = T[i - 1]
T[0] = B  

The array bounds act like wall, if you read from outside you get $0$. This is simple rewrite system, with minimal number of operations without any fancy operations, only rewrite by one calculate xor of two cells  (hey, Rule 90 takes three), and has period $262143$ giving all $18 bit$ numbers excluding $0$.

How to get such system? This is Linear feedback shift register which fits your description of PRNG, has the highest possible period ($2^L-1$) for given number of bits (cells?) minus 1, the best one would have $2^L$.