I have done something similar myself. First I tried to put the TXT record at the same domain which I did want to redirect. To tackle the CNAME problem did I come up with a complicated solution which I also did write up (https://github.com/tellnes/dhr2). But when I actually tried to use it was it too complicated.

What I'm actually using now and have been using for some time is just a simple TXT record at a subdomain (eg _redirect.example.com). I also have a script which looks for these TXT records in my zones and adds A/AAAA records when needed.

You can check it out as follows:

    dig TXT +noall +answer _redirect.infogym.no
    dig A +noall +answer infogym.no
    dig AAAA +noall +answer infogym.no
    curl -Is infogym.no | grep Location

The plan is at some point to put the scripts I actually use on GitHub, but I have never come so far.