Well after your encouragements I decided to drop into my local proper running shop today. When I arrived the shop was empty, so I told the assistant that I was looking for shoes to train up to HM distance. Also explained I use insoles from the podiatrist.
On that basis, she suggested I try on some neutral shoes, that wouldn't interfere with the insoles, and that the priority should be comfort and fit and that we should leave any gait-correction to the insoles. Sounded plausible to me, so she disappeared and came back with 2 pairs - one Saucony and one New Balance - both in the sale, and got me to try them on with my insoles. Although I prefered the look of the NB, the Saucony felt better on my feet (felt slightly more supportive) so I bought them. There was no hard sell. She did ask if I needed socks but when I said not today thanks she didn't push it.
All in all a very pleasant experience and I will no doubt be back. The shoes cost 112Euros (about 85pounds) in the sale. She said I should expect to get around 800 to 1000 km out of them and to go back if I have any trouble.