It's hard to generate priv keys without using any service. Key thing is to make sure that generation is truly random and not rigged + do it off line.
In easy terms, you need Bitcoin Core to start up, from which it directly creates a fresh wallet.dat file, where after that you can generate an address that you want to be your cold wallet address, or just a temporary address -- that easy it is, no service needed. If you want to extract the private keys from your wallet.dat file, you head over to the console and fill in the right commands.
1. Launch your bitcoin client
2. Click on 'help' in the menu bar (top right)
3. Click on 'debug window'
4. Select the 'console' tab
5. If your wallet is protected by a passphrase (i.e you have to enter a passphrase before you can send) unlock it by typing: walletpassphrase "your walletpassphrase here" 600
dumpprivkey [your Bitcoin address here]
* This will return the private key which will start with the number 5
* Once you have your private key if you had to unlock your wallet you can relock it by exiting or typing: walletlock