I've been having the same issue when I was trying to deploy a contract using truffle develop console. The contract is not extremely big but does initiate two other contracts when called a certain function. (since it's not open to the public so apologies i can't post the contract here)
I came across the error "out of gas" when I didn't specify the gas used in my 2_deploy_contract.js file, but when I gradually increased the the gas at some point I got the error "Exceeds block gas limit".
I then tried to specify the "gas" parameter in truffle.js config file. The problem is no matter how high I set it (e.g. 10000000000000) it still gave me the same error: "Exceeds block gas limit".
networks: {
development: {
host: "127.0.0.1",
from: "0x627306090abab3a6e1400e9345bc60c78a8bef57",
port: 9545,
network_id: "*", // Match any network id
gas: 18900000000000000000000000000
}
}
And the most interesting part of it is that it worked perfectly fine on Remix but not truffle develop console.