Here is a plan for all twelve keys...
If you take a simple blues melody and improvise on the changes, and then figure out the melody, memorise it, and then try to improvise on it in these four keys - C, A, F#/Gb and D#/Gb (only one at a time, mind, unless you are into polytonal blues in a big way...) - you will spend some time in all twelve keys/scales/tonal centres/modes or whatever you want to call them (they won't mind!) and you will be getting used to improvising in them.
Make it a sixteen bar blues or even a twenty four bar blues and give yourself more space on the V... I see Wikipedia gives a selection of sixteen bar blues changes. You get plenty of practice on the tonic, of course...
You could play and improvise on a blues in a different key every week - or whatever it takes, moving on when you feel you have it licked. You could spread this exploration over as long as it takes...
When you feel good about it with the four original keys, choose four different keys (those which were the V chord in the first four blues makes sense) and away you go again . Then, when you have punished that enough, using the IV chords as a starting point... you will then have give all of them a good bashing and should be pretty damn hot in all keys...
A few things will probably hit you: the more different keys you play the blues in, the better you get at hearing the changes; you are liable to get an itch of enthusiasm to learn to use favourite licks in keys you have never played them in; and you will find new licks and stuff appear as if by magic because your are trying to improvise in keys/scales you may not have used much before... which you can then transpose back into your old tried and tested keys... which gives you a very hands on, ear and fingers learning experience.
This is a step or two on from from playing licks and basic melodies around the cycle of fourths, which is also great. The more often you use the cycle, and the more ways you find to use it, the more you get out of it...
Here are the I IV V chords you will use playing a blues in these four different keys:
Blues in C - C F G
Blues in A - A D E
Blues in F# - F# B C#
Blues in D# - D# G# A# .......... or Eb Ab Bb if you prefer...
Anyone who is not vary confident at improvising yet could just play a memorised blues melody around each bunch of four keys.... start with a blues in C, say, and then try to transpose it into A, F# and D# by ear and intuition. Resort to paper if you have to, or if you want to check you are transposing the melody accurately.... whatever advances your skills. If your brain goes numb, take a break and play around with something else.....
