If you are still into improving your handwriting, buy yourself a fountain pen. It makes it a lot of fun to experiment with new characters and drastically alter your handwriting.
I've always had meh handwriting. Not horrible, but not pretty either. I've been slowly converting my scratchy characters over to smoother, more flowy characters with embelleshments, since fountain pens make it so easy to play. The process was identical to what you described. Pick a character, play with alternatives until I found one I liked, then slowly retrain myself to use it.