Without the user actually putting in their details their is no way to know if they have purchased the item. So you would need a button to invoke the purchase/restore action.
Yes Apple will reject your application if you do not have a restore button. I know first hand!
If you are opposed to having two buttons you could just make one button which states check for previous purchases, if it returns nothing then change it to a purchase button. But yeah the UX on that is not too good.
Have your normal Purchase button as your UI is designed but then put a restore button in a "settings" portion of your app. The buttons don't need to be next to each other and from what I can see this is the pattern that most apps use.
Side Note
If you have a server side implementation and your application uses some kind of login identifying the user you could track their purchases server side, when they log in again and they have previously purchased items you could trigger the restore process, If I recall correctly though the user would still have to input their Apple ID to restore with this process.