I'm unsure of what you are asking?
Are you simply after a small circuit that randomly picks between two states? (heads or tails) ?
The 555 timer circuits you mentioned, I'm pretty sure they are astable multivibrators that operate at >1khz. When the output is low, one LED is lit, and when the output is high the other..pulling its reset from low to high makes it oscillate very quickly, and when you release the button it stops. The state of the output seems 'random' because it depends on how long you hold down the button. Say if its 1Khz, a period of 1ms. If you held thge button down for an 'odd' number of mmiliseconds the output with be one state, an even number of miliseconds, the other state.
The 555 timer circuit is pretty small, and can easily fit on a bit of 1" square stripboard/perfboard. But there are transistor versions:
http://www.dieelektronikerseite.de/...ltivibrator - Eine unruhige Schaltung S01.GIF
**broken link removed**
Of course a microcontroller could do it, and with its powerdown function give you a long battery life so you hit a button, the Led's flash, then settle on one of them, and stay on for a few seconds then powers down.
Is that what you were after? Techincally of course its not random, but unless you can repeatedly hold down a button for a length of time with milisecond accuracy...it'll do
Blueteeth