Is using a rolling code as a constantly-changing shared secret effective for signing?
I'm confused at your suggestion that your clients would not have access to a public key signature facility, given that you assume that they have crypto hashes and can run code of your authorship.  More generally, the fact that you're trying to roll your own crypto doesn't bode well.

Also, I'd suggest that you have a hard look at the challenges implied by your idea of using a "one-time secure channel" to establish shared keys with your users.  What happens, for example, when one of your users tells you that their key has been compromised?  Invalidating your own copy of that key is easy, but now you need the (supposedly "one-time") secure channel once more to establish a new one.  What's the cost and inconvenience of that?

Or even worse, imagine the case where your database of pre-shared secret keys gets compromised.  You then have to establish a new shared key with every single one of your users, all at once.  Ouch.

Compare this to, say, the way GitHub uses public-key cryptography to manage access to users' repositories:


Users generate private/public key pairs on their own computer.
Users log in to the website using conventional user authentication mechanisms (e.g., passwords, security tokens, SMS, etc.)
Users can then upload public keys, or delete earlier ones that they'd uploaded.


Notice what you gain in this case:


"Self-service": users can add and delete keys at their leisure.  Now when your users' keys are compromised they just log in to your site, delete the compromised ones and upload new ones.
No secret keys are ever transmitted over the wire.  Which implies that you're never storing any secret keys on your side, so if your public key database is disclosed it's not a big deal.
You do need a user authentication system, but:


That can be outsourced (think of all those websites that allow you to log in with your Google or Facebook credentials);
Even if you built one in house, with strong user passwords and proper password storage then a compromise of your password database is would likely be much less damaging than a database of shared secret keys.





But to address your narrower questions, I'd make two observations.  First, your hash(message + secret) scheme is insecure.  Read up on HMAC, which is a standard and secure way of using a hash function as a message authentication code.

Second, you can avoid replay attacks by incorporating a counter into the message that you compute a MAC over.  No need for the random numbers; each client just keeps track of the most recent message number they received from the other party, and rejects messages numbered earlier than the most recent one.  

A good MAC will be secure against forgeries.  An attacker who sees the messages and tags (but not the key) for...

tag[1] = HMAC(key, rand[1] + message[1])
       .
       .
       .
tag[n] = HMAC(key, rand[n] + message[n])


...will not be able to forge a valid

fake_tag = HMAC(key, rand[n+1] + fake_messsage)


even if they can predict rand[n+1].  The unpredictability of the RNG's output gains you nothing.  All you need is a way to spot replays—which a counter will do just fine.