Can you unlock brand new phones? I saw a cheap Verizon HTC ONE M8 on eBay, but I am on AT&amp;T. If I was to get that phone, could I unlock it straight away? I thought I remember hearing somewhere that you can't unlock phones for a few months after their release. 

Sorry if this is the wrong site to ask.
You can unlock phones a few ways: 1) buy an unlocked phone 2) unlock via 3rd party software that will more than likely result in a voided warranty 3) wait for carrier commitment to be up and then ask them to unlock.  The thing with trying to unlock phones from different carriers though, is that Verizon is CDMA and ATT is GSM.  So with that, you can unlock the phone yes, but whether it will work on ATT (be it at all or how well) is up to you. My guess is that voice/text will work fine, but you will not get any data until you edit the APN and then it's up in the air.