Да, вместе с сообщением можно передать произвольные данные. Главное, чтобы длина сообщения, передаваемого APNS не превышала 2 кб.
Алгоритм работать будет (это, фактически, стандартный алгоритм передачи пушей). Единственное, на что следует обратить внимание - п.5: APNS не передает статус доставки сообщения. APNS предоставляет Feedback Service, с помощью которого раз в сутки (так рекомендуют Apple) можно запросить список токенов, доставка по которым более невозможна (если пользователь отключил пуш сообщения для вашего приложения). Если пользователь вновь включит пуш сообщения, данный токен может вновь стать валидным.