Your oxy/acetylene torch is way more desireable for this project. With oxy/acetylene, when you apply the flame the steel will be ready to braze in a moment or two. The flame burns somewhere in the range of 3600 degrees F.
But with a regular propane torch, I am not even sure if you could get the horshoe to brazing tempature--the flame is a) way cooler (around 1350 degrees F) and b) delivers way fewer BTUs. Part of the difference is in the heat of the flame and the other part is in the greater volume of burning gas that the oxy/acetylene set delivers.
Try the propane torch first, as an experiment and you'll see it takes a LONG time to just get the horshoe warm and even longer to make even a tiny edge red hot. Then, try your gas welding torch. You'll be convinced right away.
I would not shy away from brazing the horeshoes together--the joints will not be very noticiable and you'll get a very good result.
Another option is to weld with your torch. Your welding supplier will provide some mild steel gas welding rod.
Good wishes, David Todtman