Members of Chronic Dev Team has just released Greenpois0n RC5.4 for Mac OS X that allows you to jailbreak Verizon iPhone 4 for life. The team has posted an image of jailbroken CDMA iPhone on Verizon network which clearly shows Cydia running on it.
Follow the below guide for step by step instructions to convert your tethered jailbreak to untethered jailbreak on iOS 4.2.1:
STEP 2: Launch GreenPois0n RC5 then connect your iPhone into your Mac via USB and click onJailbreak as shown below:
STEP 3: Follow the instructions shown on the screen to enter DFU mode:
STEP 4: After the jailbreak is done, you will have a new application on your springboard called Loader. Use it to install Cydia, then it will ask you if you want to remove it. A quick re-spring, and you now have Cydia.