The original 1984 Elite computer game is famous for its huge galaxy full of planets. Each of them had individual names and descriptions such as "Lave is most famous for its vast rain forests and the Laveian tree grub."

Yet those strings were never stored as plain strings. The game had to run in 32kB of memory, so almost all strings were stored in a tokenized form and expanded using a pseudo-random number generator:

http://wiki.alioth.net/index.php/Random_number_generator

That article shows how the planet description strings were stored and reconstructed on the fly. The base representation for the aforementioned description of planet Lave was only a handful of bytes: "\x8F is \x97"

So I think Elite is a pretty good example of an application written in assembly that didn't have anything like a generic string type.