What's most probably happening is that some program is waking up your PC again. On Windows 8/8.1, when you do a regular Shutdown, what it does is actually it logs you out and then hibernates. Microsoft calls this Hybrid Shutdown/Fast Startup. You can go to Control Panel -> Power Options and uncheck the option "Turn on Fast Startup". Thereafter when you shut down using Classic Start Menu, the PC should remain off.
Alternatively, try holding down the Shift key on the keyboard while clicking "Shut down" from the Classic Start Menu. Pressing Shift while clicking Shut Down does a full shutdown (like Windows 7 and earlier did).
However, disabling fast startup is only a workaround because when you disable fast startup and do a full shutdown instead, your PC may take longer to boot. If you can find out what program is causing your PC to wake up, that will allow you to keep fast startup enabled and still shut down as usual and keep Classic Shell installed. Refer to this article:
http://www.ghacks.net/2013/12/31/find-pc-wakes-stop/ and try the various steps it covers to find out what is waking up your PC. It may be some task in Task Scheduler too. Open Task Scheduler and Event Viewer from Administrative Tools to find out what is waking up, try disabling wake timers etc.