I Feel your pain, I was in the same boat as you Sirsulu. I have had to set my iPad up as a new iPad as my first attempt at restoring failed when I named my iPad the same name as before and within an hour the new restore had a screen pop up for the activation process and I was back to square one.
THe the second time however I decided to set up with a new iPad name as this I knew would not appear in the iCloud server and bingo the fresh install of the 9.3 has worked. I have even been able to reinstall all my apps although I have lost some content in apps I still have my music (in iTunes) and my videos and pictures as I did managed to grab these using my laptop before.
I Have actually been lured into a false state of security by Apple as I always made back ups religiously until last year because I have never had an issue until now. Today I purchased further software to back up my devices, apps and all besides iTunes.
its also taught me a few things about apps that you can't back up to game clouds or localised back ups, like magazine apps, I have some now that I can never get the content back as it just doesn't exist on servers to download. I have one that I have been in contacr with the app developers and iTunes only to be told sorry sir that's £80 you wont ever see again.
when I did mine I connected it to a freshly installed iTunes, opened iTunes, plugged in the pad, held the power and the home and waited for it to go off and kept hold of the buttons til the logo came up on the pad, it then went into restore mode, I then restored it and new iPad set up.