Well, even though I appreciated the answers, I wasn't quite satisfied with the final result. I wanted my ISP changes to be transparent to my costumers and I think I managed to make it work.
Here's what I did:
I hired a cheap VPS server - VPSLink - and chose its cheapest plan: 64Mb RAM, 2Gb HD and 1Gb monthly traffic. After a lifetime 10% discount it was only US$ 7.16 per month, pretty affordable for the job and you get a sandbox VPS server as a bonus. The hosting seems so far so good - no problems. If you want to give it a shot you can either signup from its site, indicated above or through a referral code. There are a bunch available on the internet, you just need to search. Also, I can easily create one for you if you want, just leave a comment on this answer: you'll get 10% off and I a month free. I won't post the directly here because it may seem that was the intention behind this post - which was not.
This account is unmanaged but it provides root access. I then configured apache to act as a Proxy to my port 80 requests, transparently forwarding them to my local website on port 8081.
Below are some snippets of my Apache's httpd.conf config files.
VPS Server configuration:
<VirtualHost *:80>
ServerName mydomain.com
ServerAlias www.mydomain.com *.mydomain.com
RewriteEngine On
RewriteCond %{HTTP_HOST} (.*)\.mydomain\.com [NC]
RewriteRule (.*) http://mylocalserverdns.mydomain.com:8081/%1$1 [P]
</VirtualHost>
This makes request like http://subdomain1.mydomain.com/script?a=b to be transparently forwarded on server side to http://mylocalserverdns.mydomain.com:8081/subdomain1/script?a=b, so I can do whatever I want from there.
On my local server, I did the same thing to distribute my subdomains handler. I have, for instance two Java server applications that runs on ports 8088 and 8089 locally. All I had to do was another proxy forward, now internally
Local Server configuration:
<VirtualHost *:8081>
ServerName mylocalserverdns.mydomain.com
ProxyPass /app1 http://127.0.0.1:8088
ProxyPassReverse /app1 http://127.0.0.1:8088
ProxyPassReverse /app1 http://mylocalserverdns.mydomain.com:8088/app1
ProxyPass /app2 http://127.0.0.1:8089
ProxyPassReverse /app2 http://127.0.0.1:8089
ProxyPassReverse /app2 http://mylocalserverdns.mydomain.com:8089/app2
</VirtualHost>
Hope this is worth if someone else is looking for the same alternative.