What are the methods through which we can quantify the randomness or complexity in a given signal. I know spectral flatness measure (geometric to arithmetic means) is one way to do it, but what are other common techniques?
There are two different concepts:
If you think as your signal as a single random variable $X$ that is emitting values, then what you want is to calculate the Entropy of the random variable
If you are considering the entire random signal or stochastic process, then you have to estimate the autocorrelation function. The most random signal possible is White noise, in which every sample of the signal is not correlated with any other except itself.