Signature scheme with two private keys, neither derivable from the other
Well, one obvious way to do this would be using RSA with a large 'public' exponent.  That is, it is the traditional RSA sign/verify operation except that, instead of the usual optimization of having a small 'e' value, you would have a large one (a bit smaller than the modulus); and then derive d from e, p and q in the usual manner.

As for the requirement that it has no special structure, the only special structure that either exponent has is that they are odd; any odd value is a potential exponent (note: to avoid biases, it may be advisable to, when generating the p and q values, you exclude values where p-1 (and q-1) have small odd factors).

So, the signing key S would be the value (d-1)/2, and the verification key would be the value (e-1)/2, with the modulus being treated as public data (that is, there is no need to encrypt it).  That this is secure (and you can't derive one from the other) follows directly from the standard RSA assumptions. That it meets requirement 4 follows from the idea that (d-1)/2 can take on any integer value.