Unfortunately a keystore is needed to update an app in Google Play but if you have lost your keystore you will have to publish the app with a new package name and new key. You should also update the description of the original app and unpublish it.
Please note that users are allowed unlimited reinstall of each application distributed via Google Play. An application will remain available to users that have already installed it even after it has been unpublished.
Currently Google Play does not support the deletion of apps or the re-use of package names.