Which one is correct? "Having said that, why we should select an old job?" or "Having said that, why should we select an old job?", and why?
This sentence contains two clauses:
The first is a subordinate clause: this is indicated by the fact that its head is a non-finite verb, the participle having. It acts as 'supplement', a clause which plays no syntactic role in the main clause: it is not embedded in the main clause but 'anchored' to it by the fact that its subject is taken to be identical with the subject of the main clause.
The second is the main clause. Of your two choices
(1) why should we select an old job?
(2) why we should select an old job?
only (1) can act as a main clause—specifically, as a question. (2) has no subject/auxiliary inversion so it cannot be taken to be a question; since it is introduced by an interrogative it can only be parsed as free relative clause (also called a fused relative clause or in some circumstances an embedded question), which is a subordinate construction and cannot act as a main clause.
The illustration below shows how the whole thing works.