Should I consider feature scaling for all gradient descent based algorithms?
About the tips regarding plot cost vs. iteration, they are generally applicable to gradient descent approaches, including deep learning, where hyperparameter tuning (e.g. learning rate) is crucially important.

About the proper input scaling, it is not only related to the machine learning approach, but to the specific problem under consideration. Sometimes machine learning algorithms rely on distances to compute the similarity between individuals. Scaling changes some of these distances. In these cases, the resulting distance after scaling should be assessed to check whether it is more appropriate than without scaling. Here you can find examples for clustering. For some machine learning algorithms, you need standardized features, e.g. regularized linear/logistic regression. For most optimization-based machine learning algorithms, it makes sense to have feature scaling. On the other hand, there are problems where scaling doesn't even make sense (e.g. discrete input problems, like token-based natural language processing).