I'm working on memorizing the freboard myself at the moment. I'm working with a book called "Guitar Fretboard Workbook" by Barrett Tagliarino. Everything you've said SebastBerg he mentions in there. Additionally, he suggests writing things down on paper as further reinforment. The daily routine he suggests is to spend a week on each note. So week one, concentrate on A, week 2 B, etc. Each day during that week, spend 5 minutes locating every occurance of that note on the fretboard and say out loud "E on the 4th string 2nd fret, E on the 5th string 7th fret" etc. The accidentals are relatively easy since they are only a fret off the natural.

This is very similar to what SebastBerg is doing, but it gives you a variation on it.

Something else that is important is learning your alphabet backwards. Quick...what's before G? No, not A, F. Maybe it's just me, but this would mess me up. I've gotten better at it. In your idle thoughts, just say the alphabet backwards from G to A.

SebastBerg - my goal in all of this is to do exactly what you are talking about - sounding less "scaley" and learn the chord tone soloing technique. It's nice to get further confirmation that I'm on the right track :-).