Bubblestrat calculator

Back in the day when Pokevision was up you could figure out your Pokemon's exact IVs by using a proxy, but that's pretty much irrelevant, you're right in that as of now, appraisal is the closest you can get.

The problem with the Staryu is that it requires 14 attack IV. Level 1 Pokemon are rare enough. Assuming you do find a level 1 Staryu, you've now got a 1 in 8 chance of it having the IV requirements - 14 or 15 attack, and IVs range from 0-15, so 2 possibilities out of 16.

The Bubblestrat calculator also assumes the lowest IVs for the other stats (defence and stamina are irrelevant) - that 650 prestige gain is only if the Staryu has 10 CP, it could have 11 or 12 if it's other IVs are high enough, further reducing your prestige gain.

3 other options that have 0 attack IV requirement are Magnemite, Abra and Diglett, and that's why they're often the best Bubblestrat attackers, they will work in many matchups and don't have strict IV requirements. Plus their low stamina becomes an advantage in keeping their CP a few points lower.

You can use the Silph Road nest atlas to see if there's a nest of any of these near you, as well as to find optimal defenders which are usually Horsea, Poliwag and Krabby, especially Krabby, which got a CP boost because it's attack and defence was increased but it's stamina was unchanged, so it's easier to get a high CP Krabby that also has only 10 HP.

If you're not near any water, what are your usual Pokemon types not including Pidgey / Weedle / Rattata? Oddish with Razor Leaf can still work as a defender.