You class can use package protection and still implement an interface:
class Foo implements Runnable
{
public void run()
{
}
}
If you want some methods to be protected / package and others not, it sounds like your classes have more than one responsibility, and should be split into multiple.
Edit after reading comments to this and other responses:
If your are somehow thinking that the visibility of a method affects the ability to invoke that method, think again. Without going to extremes, you cannot prevent someone from using reflection to identify your class' methods and invoke them. However, this is a non-issue: unless someone is trying to crack your code, they're not going to invoke random methods.
Instead, think of private / protected methods as defining a contract for subclasses, and use interfaces to define the contract with the outside world.
Oh, and to the person who decided my example should use K&R bracing: if it's specified in the Terms of Service, sure. Otherwise, can't you find anything better to do with your time?