Bump zero fee transaction with CPFP I want to first create a transaction with 0 fee (tx1).

Next, I am going to use an output of tx1 as an input in another transaction with the necessary fees.

The issue is now that tx1 gets rejected by full nodes. Why can't I broadcast a 0 fee transaction?
In order for a node to relay a transaction, the transaction must satisfy the node's minRelayTxFee. This fee rate cut off is by default set to 1000 satoshi per kvB (= 1 satoshi per vbyte).
Your first transaction could get included in a block if the miners were aware of it, but likely it doesn't reach them.
You should try to either broadcast the first transaction with 1 sat/vbyte or to directly submit them to miners via their respective APIs.

Update 2019-09-29:
There was recently a change of the Mempool Acceptance rules merged to Bitcoin Core that allows multiple transactions to be relayed as a package. This explicitly facilitates transmission of CPFPed transactions that wouldn't usually meet the fee minimum of the receiving node.

The Bitcoin Optech Newsletter #65 describes the pull request as follows: 


  Bitcoin Core #16400 refactors part of the mempool transaction acceptance code. We don’t usually cover refactors, but this one has a tantalizing comment: “this is in preparation for re-using these validation components for a new version of AcceptToMemoryPool() that can operate on multiple transactions (‘package relay’).” Package relay could allow nodes to accept a transaction below the node’s minimum feerate if the transaction came bundled with a child transaction whose fee was high enough to pay the minimum feerate for both it and its parent. If widely deployed, package relay would allow users who create transactions a long time before broadcasting them (e.g. timelocked transactions or LN commitment transactions) to safely pay the minimum possible fee. When it came time to broadcast the transaction, they could use Child-Pays-For-Parent (CPFP) fee bumping to set an appropriate fee for the current network conditions.