Uma alternativa que acho boa seria criptografar a senha, gerar um hash para evitar que seja alterada durante o envia para o servidor e gerar uma espécie de hash de assinatura do dispositivo para que o servidor saiba que a senha veio de um dispositivo com a aplicação instalada e concatenar tudo ficaria assim:
Nunca invente sua própria criptografia! As chances de algo saírem errado são enormes. Em vez disso, use um protocolo bem estabelecido para o que quer:
Conecte-se ao seu servidor usando SSL/TLS. Assim os dados que você enviar a ele já serão confidenciais e íntegros, não é necessário nem criptografar a senha nem gerar um hash (aliás, um hash não evita que ela seja alterada durante o envio; um MAC talvez, mas isso é outra história). E se você combinar isso com uma autenticação do cliente usando certificados, você já garante a autenticidade também, bastando enviar só a senha simples mesmo e pronto!
Se precisar armazenar a senha do usuário no dispositivo (não está claro na pergunta se o usuário vai ter que digitá-la toda vez que for se conectar ao seu servidor, ou se isso ficará salvo no aparelho), procure algum recurso do próprio sistema para auxiliá-lo. Não tenho experiência com Android, mas uma busca rápida me trouxe o AccountManager
- que me parece ser um meio centralizado de gerenciar as contas que o usuário tem em diversos serviços. Sugiro dar uma estudada nele.
Detalhando
Se o que eu expliquei acima não ficou claro, deixe-me quebrar o problema em partes menores pra ficar mais fácil de entender a solução proposta (e talvez apresentar algumas alternativas):
Salvando senhas no dispositivo
A menos que você queira que o usuário entre com sua senha toda vez que for se conectar com seu servidor, é preciso que algum método de autenticação seja armazenado no dispositivo. Nesse caso, não dá pra fazer um hash da senha porque você precisa da senha no seu formato original para enviar ao servidor (do contrário o hash vira a senha, e qualquer atacante que obtenha uma cópia do hash já possui as credenciais necessárias para se autenticar com o servidor). Criptografar é uma ideia, mas onde guardar a chave? Essa é uma situação complicada, daí minha sugestão de usar o que já tem pronto no Android e tirar isso da cabeça...
Comunicando-se seguramente com o servidor
Se você não usar SSL/TLS (ex.: HTTPS), não dá pra garantir que a comunicação com o servidor não será interceptada e até modificada (em particular em redes abertas). Tentar "se virar" sem TLS vai te deixar com uma solução insegura e/ou vai te obrigar a reinventar muitas rodas. Por isso eu sugiro fortemente usar esse protocolo.
Ao criar um canal seguro via TLS, você pode enviar as credenciais do usuário em formato plano, sem a necessidade de encriptar. Pois o protocolo garante a confidencialidade (i.e. ninguém pode ler a comunicação) e a integridade (ninguém pode alterar a comunicação) de ambos, além da autenticidade do servidor (o cliente sabe que está se comunicando com o servidor certo).
Autenticando o dispositivo
Na pergunta você mostra preocupação com o dispositivo que originou a requisição ("...para que o servidor saiba que a senha veio de um dispositivo com a aplicação instalada..."). Ou seja, além de autenticar o usuário com o servidor, você também quer autenticar o dispositivo com o servidor.
A princípio, isso também pode ser feito via SSL/TLS, com o uso de certificados do cliente. Grosso modo, ao instalar a aplicação ela geraria um certificado para aquele dispositivo, registraria esse certificado no servidor (ou simplesmente teria aquele certificado assinado por uma CA que o servidor confia), e então ao se comunicar via TLS utilizaria esse certificado com o protocolo. Assim ambos cliente e servidor estariam autenticados entre si, e bastaria então você autenticar o usuário (enviando a senha em seu formato normal).
Se tudo isso for muito complicado, uma alternativa mais simples seria gerar uma senha aleatória pra ser a "senha do dispositivo", e cadastrá-la no servidor junto à senha do usuário. Essa senha seria então enviada durante a autenticação, também sob o canal seguro estabelecido anteriormente.
Salvando senhas no servidor
No servidor, naturalmente, você não vai guardar a(s) senha(s) em formato plano, mas sim um hash da(s) mesma(s). Veja a pergunta "Como fazer hash de senhas de forma segura?" para mais detalhes.