In this paper, we consider composite convex minimization problems. We advocate the merit of considering Generalized Proximal gradient Methods (GPM) where the norm employed is not Euclidean. To that end, we show the tractability of the general proximity operator for a broad class of structure priors by proposing a polynomial-time approach to approximately compute it. We also identify a special case of regularizers whose proximity operator admits an efficient greedy algorithm. We then introduce a proximity/projection-free accelerated variant of GPM. We illustrate numerically the benefit of non-Euclidean norms, on the estimation quality of the Lasso problem and on the time-complexity of the latent group Lasso problem.