The "right" way to think about renewals is to ask yourself why you want to renew.
As I understand it, you have a root CA which is hardcoded in some application installed in the clients. Moreover, the clients themselves own certificates, presumably issued (directly, or indirectly through an intermediate CA) by that root CA. This hints at some mutual authentication setup, e.g. some SSL with certificates on both the client and the server. The important point to remember is that when you own a certificate (i.e. you know the corresponding private key), then you don't have to validate that certificate; your certificate is for the benefit of other people, not you. In particular, clients don't need to trust or even know the root CA in order to use their own certificates; they need to trust the root CA to verify a certificate sent to them (e.g. a certificate presented by a SSL server to which the clients connect).
Therefore, the notions of "root CA update" and "client certificate update" are really unrelated to each other. It will be simpler to think about both kinds of renewals in a separate way.
For root CA update, we have the following setup: an application has been deployed, and contains the root CA name and public key, hardcoded in the application. This is called, in X.509 terminology, a trust anchor. The application uses that TA to validate incoming certificates (e.g. SSL server certificates).
For some reason, you want to change the TA name or key or both. The normal mechanism for that is an update of the application. It would be inordinately naive to believe that a given deployed application is free of bugs, and if it is involved in security-related actions, then bugs can turn into vulnerabilities. So you must have some update mechanism which allows the safe replacement of the application binary with a newer version. Some software distribution platforms (e.g. Google Play for Android, or the packages for a Linux distribution) provide such a mechanism.
By definition, the application binary is trusted (since it is that code that manipulates the sensitive data) so the update mechanism must be protected against hostile alterations. Thus, embedding the new TA in the application and pushing it as an update is the primary (and, really, the only) method by which you can "renew the root CA".
If the outer platform does not provide for a safe update mechanism, then you must build your own. This may be as crude as sending a new cdrom to each user... But if you want to automate things, you will need either a signature or at least some authentication. For instance, the application could connect to a specific HTTPS server (which implies some validation of the server certificate) to download the update, reputed correct since it comes from the specific update server.
The reason why you need to push a new root CA is important, especially with regards to timing. There are two main cases: either you need to react fast because the root CA key was compromised, or you have time (e.g. you want to change the CA key for a longer one because the one you used becomes a bit too short with regards to cryptanalytic advances):
If you have time, then you can sign the new application binary (which includes the new root CA) with the old CA. This will allow for a smooth transition.
If you do not have time (e.g. root key compromise), then you are in deep trouble. The best you can do is handle it as a "critical vulnerability" and make a lot of fuss about it so that users manually connect to some distribution server (protected with a "mainstream SSL certificate" that you buy for a hundred bucks) to download the new application.
This is still a very bad situation and you would prefer not to encounter it. The classic way to keep your root CA key safe is to keep it offline: never plug the root CA to some network. This means that your PKI must have an online intermediate CA to issue the users' certificates. You manually (i.e. with USB flash drives) obtain CRL from the root CA as a regular procedure (e.g. on a weekly basis).
Alternatively, apart from the root CA, you may keep in an offline machine an unrelated "update package signature key" which you use when you need to build and distribute a new version. The application binary would contain a copy of the corresponding public key, which has nothing to do whatsoever with your root CA key and certificates; it is like an "extra root" used only to verify application update packages. Being kept offline at all times, that machine should be safe from remote attackers, and thus you may work on the assumption that the package signature key will not be compromised.
All other things being equal, it is best if you never renew the root CA key. As far as we know, a 2048-bit RSA key ought to be good for a substantial number of decades, and may be broken only by yet undiscovered but devastating attacks. There is no indication, currently, that such attacks will be discovered in the future or even if they exist at all; and there is no indication either that a longer CA key would fare any better (that's the problem with speculation on unknowns: it is speculative and rarely yields any useful information).
For client certificate renewals, the problem is completely different. A client certificate is not something that the client itself trusts.
Since a client certificate contains the client identity and public key, a first "renewal" method is to simply have the CA renew the certificate on its own accord, by taking the old, changing the validity dates, and signing it again. The client key and name are thus unchanged. The "renewal issue" has been reduced to the question of pushing the new certificates to whoever needs to know it. Usually (but not necessarily), it is best if the client itself knows its own certificate, because it allows the client to send that certificate as part of some network protocols (e.g. in SSL/TLS, when the client uses a certificate for authentication, the server learns that certificate by virtue of the client sending it).
Certificates contain only public data and are signed, meaning that they can travel safely on the Internet. You just need to setup some regular, plain HTTP request by which a client may ask some server whether a new certificate exists, and obtain it. For that mechanism, the client may contain a copy of the issuing CA public key, or some higher CA, in order to check that the certificate is the right one -- the client does not trust the root CA, but you want to avoid wanton disruption by ill-intentioned attackers who corrupt renewed certificates while in transit: this would be a DoS attack. An altered client certificate will not be accepted by any server, but it is best if the client application notices the foul play upon certificate download rather than later, upon certificate usage.
The reason why you want to renew the client certificate is, again, important:
The official reason for enforcing end-of-validity dates in X.509 certificates is to make sure that revocation lists (CRL) don't grow indefinitely. The less official reason is that one-year certificates ensure yearly renewals, that can be turned into yearly access fees. If you renew client certificates for these reasons, then you can renew on the CA side as explained above.
If you need to change the client key, then you are reacting on some abnormal and exceptional situation, e.g. a client key compromise. In that case, the client has just lost its main method to demonstrates its identity to any server, in particular your CA.
At that point, you have to consider how you issued the certificate in the first place. A certificate binds an identity to a public key, so you had, at that time, a way to verify the purported client identity. The generic recovery method after a private key compromise is thus using the same initial authentication method again. At that point, the user is normally actively collaborating -- after all, the compromise is normally discovered by the user himself.
Details on the possible emergency recovery methods vary a lot, depending on your context. When the notion of identity that your PKI uses is "same user" (anybody can register and there is no formal physical identity, but a user should be able to demonstrate that he is the same user as previously), a practical method is to issue, along with the initial certificate, a "recovery code" that the user writes down on a piece of paper, and types again when he has lost exclusive control of his private key: either the private key is known to some attacker, or the user's phone broke down and he cannot use the key anymore, or both (typical case: the user's phone or laptop has been stolen). The recovery code is the method by which the user can demonstrate to the CA that he is the same user as the one who previously owned the certificate that is to be renewed.