Need to change the subdomain URL structure - D7
I believe you will still need some mod_rewrite redirection rules (RewriteRule), but only after the fact; it can be used used to ensure users accessing subX.example.com get redirected appropriately to the new content URL instead of mod_rewrite being the solution to the problem (which, as you mentioned, is not what you wanted).

Have you tried using pathauto to set a URL pattern and then using views_bulk_operations to mass update node aliases? I recall VBO will overwrite any existing alias, but if it doesn't simply make a database backup for good measure and then drop your existing node path aliases from the database directly as they will be regenerated anyways using VBO.

If you need to create redirects from the old node aliases to the new ones (ignoring the hostname component), the redirect module will automatically create 301s.

Here is a quick guide on pathauto + VBO: http://drupal.org/node/1326928