If your blues uses A7, D7, E7, or just A, D, E (standard major chords), you can play an A pentatonic bluesscale (A, C, D, D# -the blue note-, E, G) on all chords, but you can also 'follow' the chords and play a D pentatonic bluesscale (D, F, G, G#, A, C) on D7, and E pentatonic blues (E, G, A, A#, B, D) on E7. This will also work on a minor blues (Am, Dm, Em or Am7, Dm7, Em7)and will sound 'right', although taste is everything, ofcourse.
If your blues consists of dominant chords (in A: A7, D7, E7), a jazz-aproach is to use an A-mixolydian scale on A7, D-mixo on D7 and E-mixo on E7. Look up what notes these scale have and what patterns they have on the fretboard, if you don't know. If you've never used these scales before, they will take some getting used to and it will take -a lot of- training before you smoothly 'follow' the chords.
To avoid sounding predictable you shouldn't start -as you said- on the chord note when the chord changes. You can train yourself in a million ways, but with the pentatonic scales, for example try starting on the minor third when the chord changes, so C on A, F on D and G on E, and then train all the other notes as a starting point (fourth, raised fourth, fifth etc.) and just let your ear decide what you're going to play after the first note. Starting on the third (or fourth, fifth, etc.) each time can in itself become predictable, so when you've got this down, mix them up. A good training to avoid predictability is starting on different (up- and down) beats in the bar as well.
This has become a very long answer.... Hope you can use it.