Well, it will come. There's a time to worry about staying in key, and theres a time to listen, use your ear, and just play. Ideally it all comes together at somepoint in effortless application...

Here's a lesson I teach my students called 5 steps to more interesting solos.

Step 1. When aimlessly blathering through scales, learn at least 5 different finger patterns of the scale along the length of the neck. Don't stay in any one pattern for too long. That's usually really boring. Keep moving between finger patterns. Different positional patterns of the same scale cause you to combine the same notes in different ways. Making a short statement in one pattern and then moving to another pattern forces a break between ideas, which is the beginning of thinking about phrasing. It also causes you to use different registers of the instrument... high, low, and middle. It also looks more interesting to travel around the whole length of the neck.

Step 2. Learn a lot of those boring, mechanical sequence patterns like ascending and descending in 3rds or 4ths or 6ths, the 3 step pattern [123, 234, 345, 456, 567, 678, 789] and the 4 step [1234, 2345, 3456, 4567], the 1-2-3-1 sequence, the reverse 3 step [321, 432, 543, 654], etc. There are whole books full of dozens of these and they're pretty dry, tedious, and boring. But these exercises force your fingers and ears to combine notes in different ways than your fingers will do naturally. If you merely alternate in short bursts between aimlessly blathering and mechanically sequencing in 5 different positions on the neck, you already are creating more interest because there is musical contrast between the aimlessness of the blathering and the mechanical structure of the sequences.

Step 3. This step is so obvious that you should kick yourself in the pants for not spending more time doing it endlessly. Steal licks. Steal licks all the time. Steal licks from the best guitar players ever. Steal licks from other instruments. Learn to play these licks in any key and in many spots on the neck, not always starting on the same string or on the same finger. There are books and videos full of licks. Licks slowed down so you can learn them. Licks, licks, licks. You can never have a big enough vocabulary of licks. Get busy learning licks. In many different styles. You can even make up your own. But at first, steal licks all the time.

Step 4. This next step is simple and obvious and many guitarists don't think of exploiting the variety of these easy items. I call them guitarisms. NCP mentions a number of them above.

1. bending [there are lots of different ways]
2. vibrato [there is more than 1 kind]
3. sliding [glissando] and dive bombing
4. hammer-ons
5. pull-offs
6. trills
7. tremolo picking
8. harmonics
9. pinched harmonics
10. false harmonics
11. palm muting
12. deadened string/scratchy noises
13. raking and sweep picking
14. right-hand finger tapping
15. pick scrapes
16. behind the nut noises
17. beating on the guitar like a hand drum
18. rasgueado strumming
19. picking near the bridge
and more I can't think of off hand...

If you aren't exploiting the variety of these, or you are stuck on one of them too much, then you are boring. Get with it. They are like spices in food. Use them judiciously, but enhance the flavor of your guitar playing. Please.

step 5. Take all of the musical elements that fit on a guitar... rhythm, note values, timbre, tone, arpeggios, intervals, chords, quoting melodies, articulation and picking techniques, embellishment, alteration, repetition, superimposition, dissonance, resolution, consonance, harmony, lyricism, rests and silence, minimalism, form, shape, structure, ethnic influences, and anything you can think of, read about, stumble across and discover... and mess around with them. Creativity simply means goofing off with this stuff. Learn to let go of structured approaches and just have fun playing like a child. You may be surprised by what bubbles up from your subconscious. Don't forget to have fun.

There are also creativity exercises you should investigate, like SCAMPER:

S = Substitute? (What can I get rid of, eliminate, or subtract?)

C = Combine? (How can I combine X with Y? What would happen if I combine this idea with that idea?)

A = Adapt? (What if we change this?)

M = Modify? = Magnify?

P = Put to other uses?

E = Eliminate or minimize?

R = Reverse? = Rearrange?

There is also, now, absolutely no excuse for not watching tons of instructional guitar videos. Get busy, slackers!