The participle of ''to shall'' is ''should'' in English so ''I shall'' changes into ''I should''. In dutch ''ik zal'' changes to ''ik zou'' but the difference is that ''ik zou'' does not mean ''I should'' but rather ''I would''.
''Wat zou ik kiezen?'' thus means ''What would I choose?''. In order to convey the meaning of ''I should'' you need to add another verb in Dutch which is ''moeten'' so you get ''wat zou ik moeten kiezen?'' or you could simply go with ''wat moet ik kiezen?''. You are right that it could also mean "What should I have to choose?" though.
Totally agree, it is the most literal translation of the sentence and it is not wrong. The meaning of this English sentence is different though. What would I have to choose would be the question you ask if you want to order something from a list of items, where some things are optional and others are not, and you want to know which are the ones in the optional category. Example the accessories of your car once you have selected a basic model. Do I have to decide the number of doors or are there always 4 on this type? The sentence what should I choose means something like: please help me make a decision. Shall I buy this type of car or another one?