What do you mean 'non existent Apple id' ? Accounts can't be deleted, unless you asked iTunes Support to do so and they agreed.
If you can't get the account's password reset via http://iforgot.apple.com (e.g. by answering its security questions), then do you have an Apple store nearby that you could go to (make a Genius Bar appointment), if not then try contacting iTunes Support : http://www.apple.com/support/itunes/contact/ - click on Contact iTunes Store Support on the right-hand side of the page. Either at a store or online they are likely to want to see proof of ownership of the phone (e.g. original receipt with its serial number) before they might remove the phone from the account.