Gauge or Histogram - Which is a more suitable metric for determining load of a pod?

If I'd need to choose one of your approaches I would probably choose the first approach.

But I'd probably change the path here.

Instead of using the applications' metrics to decide how many jobs/pods you need I would probably use the queue's metrics.

For that, I used KEDA and I recommend it. Using KEDA can help you scaling your solution and keep using Prometheus only to keep track of what's happening.

KEDA supports Jobs or Deployments. Jobs (ScaledJob) have advantages over deployments (ScaledObject) in some cases. For example, if you can use jobs, you can also leverage from scaling ephemeral nodes or scaling from zero nodes to the needed node count.