"He went out for fishing" is not natural English. "He was cruising for bruising" doesn't sound familiar to me. As you say, the expression is "cruising for a bruising".
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.