Conan was Cimmerian, and as in Howard's myths the Cimmerians were the primary ancestors of the Celts and most specifically the Gaelic branch, a highlands Scots accent would be most appropriate.
Note that Conan never loses his barbaric accent, no matter whether he be general or king. You can take the barbarian out of the highlands, but you can't take the highlands out of the barbarian...
I've always felt that the best way to find the next actor to portray Conan is to troll the drunk tanks of the eastern towns of Scotland, where North Sea oil rig roughnecks on leave would be stuck after a night of carousing and fighting. Look for the black-haired, blue-eyed burly Scots roustabout that the other inmates defer to and fear, and that's your man for the part...