Is it possible to generate address and private key pair completely offline, using only dice / other random number generators, calculators, paper and pen? If yes, whats the procedure and formulas used?
Yes, it is possible to create such keypairs offline, but the calculations are long and complex. You would need to find out how to:
1) Create a secp256k1 public key from a private key
2) Perform SHA-256 hashing
3) Perform RIPEMD-160 hashing
4) Be able to convert the final value into Base 58
Generally, the calculations would be very tedious; this is what we have computers for.
A good article on keypair generation http://www.swansontec.com/bitcoin-dice.html
Essentially, you can generate your private key using dice, and use a computer to derive an address from that private key.
Here are instructions to create a Bitcoin address and associated key-pair completely offline. It is straight from the Bitcoin Wiki.
This working computer example complements @ThePiachu.
Let's assume your random number generator mechanism generated this very low entropy 256-bit number in hexadecimal format that will become the private key:
1. Associated compressed Bitcoin WIF-encoded private key:
% echo "0000111122223333444455556666777788889999aaaabbbbccccddddeeeeffff" | sed 's/$/01/' | bx base58check-encode -v 128
2. Associated compressed Bitcoin public address:
% echo "0000111122223333444455556666777788889999aaaabbbbccccddddeeeeffff" | bx ec-to-public | bx ec-to-address -v 0