I agree that another dog probably wouldn't help with his howling and separation anxiety. I think it would be better to sort out his issues before even considering another dog.

What our trainer told us to do with Millie when she behaved this way was to ignore her before we left the house, we don't say goodbye, no attention before we leave at all. We also dropped treats around us as we were getting ready to leave, without obviously letting her see us drop them. That way, leaving became a good thing, but since she didn’t see us actually drop them she didn’t associate the treats with us leaving and then them ending. Make sense? It actually worked really well, and fairly fast. Now they both ignore us when we leave and usually sleep through our departure.

I think that Prozac may be a good stepping stone with Lefty to get him to a point where he’s more open to your training.